时间空间复杂度

排序是算法中最经典的问题，以下表格对插入排序、冒泡排序、选择排序、希尔排序、快速排序、归并排序这几种排序进行了比较。

排序算法 平均时间复杂度 最坏时间复杂度 空间复杂度 是否稳定
插入排序 O（n2） O（n2） O（1） 是
冒泡排序 O（n2） O（n2） O（1） 是
选择排序 O（n2） O（n2） O（1） 不是
希尔排序 O(nlogn) O（n2） O（1） 不是
快速排序 O(nlogn) O（n2） O（logn） 不是
归并排序 O(nlogn) O(nlogn) O（n） 是

下面是具体的javascript实现：

插入排序 Insertion Sort

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个形成一个新的、记录数增1的有序表。

插入排序还有升级版-二分插入排序（Binary Sort)。即数据在试图找到自己在前面已排序的部分中的位置时，用比较高效的二分查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var insertSort = function (arr) {
    var len = arr.length, key;
        for (var i = 1; i < len; i++) {
            var j = i;
            key = arr[j];
            while (--j > -1) {
                if (arr[j] > key) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + 1] = key;
        }
};

冒泡排序 Bubble Sort

重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序错误就把他们交换过来。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var bubbleSort = function (arr) {
    var flag = true;
    var len = arr.length;
    for (var i = 0; i < len - 1; i++) {
        flag = true;
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                var temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
                flag = false;
            }
        }
        if (flag) {
            break;
        }
    }
};

选择排序 Selection Sort

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var selectSort = function (arr) {
    var min;
    for (var i = 0; i < arr.length - 1; i++) {
        min = i;
        for (var j = i + 1; j < arr.length; j++) {
            if (arr[min] > arr[j]) {
                min = j;
            }
        }
        if (i != min) {
            swap(arr, i, min);
        }
    }
};
function swap(arr, index1, index2) {
    var temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
};

希尔排序 Shell Sort

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止 

1
2
3
4
5
6
7
8
9
10
11
12
var shellSort = function (arr) {
    var gaps = [5, 3, 1];
    for (var g = 0; g < gaps.length; ++g) {
        for (var i = gaps[g]; i < arr.length; ++i) {
            var temp = arr[i];
            for (var j = i; j >= gaps[g] && arr[j - gaps[g]] > temp; j -= gaps[g]){
                arr[j] = arr[j - gaps[g]];
            }
            arr[j] = temp;
        }
    }
};

快速排序 Quick Sort

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var quickSort = function(arr, left, right) {
    var i, j, t, pivot;
    if (left >= right) {
        return;
    }
    pivot = arr[left];
    i = left;
    j = right;
    while (i != j) {
        while (arr[j] >= pivot && i < j) {
            j--;
        }
        while (arr[i] <= pivot && i < j) {
            i++;
        }
        if (i < j) {
            t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    }
    arr[left] = arr[j];
    arr[j] = pivot;
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

归并排序 Merge Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
function mergeSort(arr) {
    if (arr.length < 2) {
        return;
    }
    var step = 1;
    var left, right;
    while (step < arr.length) {
        left = 0;
        right = step;
        while (right + step <= arr.length) {
            mergeArrays(arr, left, left + step, right, right + step);
            left = right + step;
            right = left + step;
        }
        if (right < arr.length) {
            mergeArrays(arr, left, left + step, right, arr.length);
        }
        step *= 2;
    }
}
function mergeArrays(arr, startLeft, stopLeft, startRight, stopRight) {
    var rightArr = new Array(stopRight - startRight + 1);
    var leftArr = new Array(stopLeft - startLeft + 1);
    k = startRight;
    for (var i = 0; i < (rightArr.length - 1); ++i) {
        rightArr[i] = arr[k];
        ++k;
    }
    k = startLeft;
    for (var i = 0; i < (leftArr.length - 1); ++i) {
        leftArr[i] = arr[k];
        ++k;
    }
    rightArr[rightArr.length - 1] = Infinity; // 哨兵值
    leftArr[leftArr.length - 1] = Infinity; // 哨兵值
    var m = 0;
    var n = 0;
    for (var k = startLeft; k < stopRight; ++k) {
        if (leftArr[m] <= rightArr[n]) {
            arr[k] = leftArr[m];
            m++;
        } else {
            arr[k] = rightArr[n];
            n++;
        }
    }
}

js 中 Array.prototype.sort 的实现

ECMAScript没有定义使用哪种排序算法，甚至没有规定排序的稳定性，各个浏览器的实现方式也会有所不同。
具体到浏览器中，
Mozilla/Firefox : 归并排序
V8 ：数组长度小于等于 22 的用二分插入排序，其它的用快速排序（array.js test 源码），数组长度大于1000时会 调用 GetThirdIndex 获取更接近中位值的 pivot

见下面注释

1
2
// Quicksort is used for arrays which length > 22
// Arrays which length > 1000 guarantee GetThirdIndex is executed

更新于 20210419，v8的排序算法已变更为 tim-sort

(array-sort.js源码)[https://github.com/v8/v8/blob/master/third_party/v8/builtins/array-sort.tq]

Tim Sort采用分治的思想，分组进行二分插入排序，再用归并排序合并。