虽然我们有了Array.prototype.sort()，但是要知其所以然。

Sedgewick在《算法中提到了》学习排序算法的意义：

  • 对排序算法的分析有助于全面理解算法性能的不计较
  • 类似的技术也能有效解决其他类型的问题
  • 排序算法往往是解决其他问题的第一步

辅助工具

为了方便算法的比较与测试，封装常用方法至utils.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
module.exports = {
    //生成长度为size，最大值为max的正整数列
    makeNum(size, max) {
        let out = []
        for (let i = 0; i < size; i++) {
            let n = 1 + Math.floor(Math.random() * max)
            out.push(n)
        }
        console.log(`生成的数组为：${out}`)
        return out
    },
    //交换数组中两数位置
    exchange(arr, pos1, pos2) {
        let temp = arr[pos1]
        arr[pos1] = arr[pos2]
        arr[pos2] = temp
    }
}
  • Q&A:为什么要引入交换（exchange）？

如果可以，尽可能在原数组上交换，而不是开辟新的数组，以减少内存耗费

选择排序

选择排序的核心思想是极简的，即外循环从头逐位向后推进中，内循环从外循环头部之后找到一个最小的元素跟头部元素交换，如此进行下去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const utils = require('./utils')

function selectSort(arr) {
    let len = arr.length,
        times = 0
    console.time('选择排序')
    for (let i = 0; i < len; i++) {
        let min = i
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[min]) {
                exchage(arr, j, min)
            }
        }
    }
    console.timeEnd('选择排序')
    return arr

}

插入排序

插入排序的思想类似于打扑克牌，从头开始，异次挑外循环元素进内循环中对比，直到该元素在内循环中插入到合适的位置。对比过程中该元素可能不断向左。插入排序常数性快与选择排序。

1
2
3
4
5
6
7
8
9
10
11
12
function insertSort(arr) {
    let len = arr.length,
        times = 0
    for (let i = 0; i < len; i++) {
        for (let j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
            utils.exchage(arr, j, j - 1)
            times++
            console.log(`第${times}次修改，数组为${arr}`)
        }
    }
    return arr
}

希尔排序

希尔排序是插入排序的带间隔翻版，核心思想是以固定间隔分隔数组，在分隔出的子数组中应用插入排序。一轮之后，再缩小间隔继续排序，直到间隔为1。

经本人测试，希尔排序在随机自然数列的排序中快过Array.prototype.sort()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function shellSort(arr) {
    let len = arr.length,
        gap = 1
    console.time('希尔排序')
    //根据数组长度动态生成一个适合的间距
    while (gap < len / 3) {
        gap = gap * 3 + 1
    }
    while (gap >= 1) {
        for (let i = gap; i < len; i++) {
            for (let j = i; j >= gap && arr[j] < arr[j - gap]; j -= gap) {
                utils.exchange(arr, j, j - gap)
            }
        }
        gap = Math.floor(gap / 3) //在一次长度为gap的插入排序完调整gap
    }

    console.timeEnd('希尔排序')
    return arr
}

归并排序

归并排序在牺牲了一定内存（使用了辅助数列）的情况下，实现了时间复杂度为(NlgN)，是一种稳健的排序方法。其核心是使用分治的思想，递归地将大问题化小，用小问题的答案解决大问题。而归并排序另外一个问题在于引入了递归，会受到常规语言的调用栈限制（如chrome67，V8引擎:约13000次）。

下面先给出实现，为了理解其分治的过程，打印过程以便观察

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
const utils = require('./utils')

function mergeSort(arr) {
    console.log(`slice:[${arr}]`)
    let len = arr.length
    if (len < 2) {
        return arr
    }
    let mid = Math.floor(len / 2),
        left = arr.slice(0, mid),
        right = arr.slice(mid)
    return sort(mergeSort(left), mergeSort(right)) //子数组继续递归拆分,然后再合并
}

function sort(left, right) { //合并两个子数组
    console.log(`sortLeft:[${left}],sortRight:[${right}]`)
    let result = []
    while (left.length && right.length) { //当左右栈还未用尽时，继续排序
        let item = (left[0] <= right[0]) ? left.shift() : right.shift() //排序的核心步骤，为保证稳定，判断条件为<=
        result.push(item)
    }
    return result.concat(left.length ? left : right)
}

let a = utils.makeNum(5, 100)
console.log(mergeSort(a))

输出如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
> node merge.js
生成的数组为：9,21,65,77,55
slice:[9,21,65,77,55]
slice:[9,21]
slice:[9]
slice:[21]
sortLeft:[9],sortRight:[21]
slice:[65,77,55]
slice:[65]
slice:[77,55]
slice:[77]
slice:[55]
sortLeft:[77],sortRight:[55]
sortLeft:[65],sortRight:[55,77]
sortLeft:[9,21],sortRight:[55,65,77]
[ 9, 21, 55, 65, 77 ]

可以看到，开始算法先对数组切分，产生一个以原数组为根的树形结构，树枝粒度为1。以深度优先的方式触底，返回后进入Sort环节进行排序操作，得到有序的大数组，最后汇聚成有序的数组。

归并排序

快速排序

快速排序应该是当今使用最广泛的一种排序。顾名思义，其效率高，且占用内存少。其内循环小于绝大多数算法。类似于归并排序，其核心思想依然为分治。简要的说就是选数组中任意一点进行分割(partition)，然后将大于该点值得元素放置于元素左边，小于的放于右边。

  • 归并排序：递归调用发生在处理整个数组之前
  • 快速排序：递归调用发生在处理整个数组之后

快速排序的代码如下

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
const utils = require('./utils')

function quick(arr, lo, hi) {
    var lo = typeof lo === 'number' ? lo : 0,
        hi = typeof hi === 'number' ? hi : arr.length -1,
        index
    if (lo < hi) {
        //先分割，再递归调用
        index = partition(arr, lo, hi)
        quick(arr, lo, index - 1)
        quick(arr, index + 1, hi)
    }
    return arr
}
//以arr[lo]为默认分割点，在比较过程中，分割点绝对位置不变
function partition(arr, lo, hi) {
    //pivot为当前分隔游标，随着符合判断条件不断前进
    var pivot = lo
    for (var i = lo + 1; i <= hi; i++) {
        //如果有小于比较点的元素，交换至左边
        arr[i] < arr[lo] && utils.exchange(arr, i, ++pivot)
    }
    //最后，将分割点[lo]移至正确位置
    utils.exchange(arr, pivot, lo)
    return pivot
}

各种排序算法的比较

在熟知各种算法的优缺点后，我们可以根据实际问题的需要选择最合适的排序算法。其中考量点包括问题规模，数组有序程度以及空间限制等等。

算法 时间复杂度 最好 最坏 空间复杂度 稳定性*
选择 O(n^2) O(n^2) O(n^2) 1 不稳定
冒泡 O(n^2) O(n) O(n^2) 1 稳定
插入 O(n^2) O(n) O(n^2) 1 稳定
希尔 不确定 O(n) O(n^2) 1 不稳定
归并 O(nlogn) O(nlogn) O(nlogn) N 稳定
快速 O(nlogn) O(nlogn) O(n^2) lgN 不稳定
堆 O(nlogn) O(nlogn) O(nlogn) 1 不稳定

*注：稳定性指在排序完成后，值相等的两个元素会不会改变相对位置，若改变则为不稳定。反之稳定。