本文通过JavaScript语言实现了插入排序、冒泡排序、快速排序和归并排序四种经典算法。文章仅展示代码实现与时间复杂度分析，未深入讲解算法原理。其中特别指出JS中需手动处理整数取整的问题，并提供了各算法的基础代码片段供参考。
排序算法概述
排序算法的实现
由于本人的JavaScript水平有限，因此这里采用类似Java和C语言的编程风格来编写排序算法。
此外，本文不涉及算法原理的详细讲解，仅专注于代码实现。代码中可能存在Bug，欢迎通过博客评论进行指导与指正。 插入排序
插入排序实现
插入排序（Insertion-Sort）是一种简单直观的排序算法。其核心思想是构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。在实现上，插入排序通常采用原地排序（in-place），即仅需O(1)的额外空间。因此，在从后向前扫描的过程中，需要反复将已排序元素逐步向后移动，为最新元素腾出插入空间。
具体实现代码如下：
function insertSort(arr) {
if (!arr) return;
var len = arr.length;
if (len == 0 || len == 1) return;
for (var i = 1, len = arr.length; i < len; i ++) {
var stand = arr[i];
for (var j = i - 1; j >= 0; j --) {
if (arr[j] > stand) {
arr[j + 1] = arr[j];
} else {
arr[j + 1] = stand;
break;
}
}
}
return arr;
}
该算法的时间复杂度为：O(n^2)
当然，该算法仍有优化空间，例如可以将搜索替换位置的逻辑改为二分查找。 冒泡排序
冒泡排序实现
这是一个经典的排序算法。提到冒泡排序，我不禁感到心痛。本科时期曾撰写关于冒泡排序改进的论文，但论文完成后竟无法完整实现该算法，实在令人尴尬。
if (!arr) return;
var len = arr.length;
if (len == 0 || len == 1) return;
for (var i = 0; i < len; i ++) {
for (var j = 0; j < len - i - 1; j ++) {
if (arr[j] > arr[j + 1]) {
var tmp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = tmp;
}
}
}
return arr;
}
该算法的时间复杂度为：O(n^2) 快速排序
快速排序实现
这是一个非常经典的排序算法，其排序过程主要分为三步：
- 从数列中选取一个元素作为“基准”（pivot）；
- 重新排列数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆放在基准后面（相同数值可置于任意一侧）。分区操作结束后，基准元素即处于数列的中间位置；
- 递归地对小于基准值元素的子数列和大于基准值元素的子数列进行排序。
具体实现代码如下：
function quickSort(arr, bt, ed) {
if (bt < ed) {
var pivot = findPartition(arr, bt, ed);
quickSort(arr, bt, pivot - 1);
quickSort(arr, pivot + 1, ed);
}
}
function findPartition(arr, bt, ed) {
var stand = arr[bt];
while (bt < ed) {
while (bt < ed && arr[ed] >= stand) {
ed --;
}
if (bt < ed) {
arr[bt ++] = arr[ed];
}
while (bt < ed && arr[bt] <= stand) {
bt ++;
}
if (bt < ed) {
arr[ed --] = arr[bt];
}
}
arr[bt] = stand;
return bt;
}
该算法的时间复杂度为：O(nlogn)。 归并排序
归并排序实现
这也是一个非常经典的排序算法，我借此学习JavaScript的机会复习经典排序算法。关于归并排序的思想，可参考我的另一篇博客：归并排序。此处仅展示JavaScript的实现方式。
function mergeSort(arr, bt, ed) {
if (bt < ed) {
var mid = bt + parseInt((ed - bt) / 2);
mergeSort(arr, bt, mid);
mergeSort(arr, mid + 1, ed);
mergeArray(arr, bt, mid, ed);
}
}
function mergeArray(arr, bt, mid, ed) {
var mArr = [];
var i = bt, j = mid + 1;
while (i <= mid && j <= ed) {
if (arr[i] <= arr[j]) {
mArr.push(arr[i++]);
} else {
mArr.push(arr[j ++]);
}
}
if (i <= mid) {
mArr = mArr.concat(arr.slice(i, mid + 1));
}
if (j <= ed) {
mArr = mArr.concat(arr.slice(j, ed + 1));
}
for (var h = 0; h < mArr.length; h ++) {
arr[bt + h] = mArr[h];
}
}
在编写归并排序时有一个小插曲：JavaScript不会自动取整，因此后来使用了parseInt方法，感觉非常有趣。