前言

排序在前端用的也不多，不过偶尔也用。面试官考的比较多的算法也是排序方法。

冒泡排序

冒泡排序是最基础的排序方法，其实就是遍历每一个数组元素，进行二次内循环进行排序。非常简单，直接上代码：

/**
 * 冒泡排序
 * @param {*} list 
 * @returns 返回排序后的数组（也是传进来的数组） 
 */
function bubbleSort(list) {
    const len = list.length
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len - 1; j++) {
            if (list[j] > list[j+1]) {
                let temp = list[j]
                list[j] = list[j + 1]
                list[j + 1] = temp
            }
        }
    }
    return list
}

上面的代码非常的简单。测试一下：

const sourceList = []
const len = 100000
for (let i = 0; i < len; i++) {
    // 得到 0 至 len 的随机整数
    let int = Math.floor(Math.random() * (len + 1))
    // 放入数组
    sourceList.push(int)
}
console.log(sourceList)

const startTime = new Date().getTime()
let result = bubbleSort(sourceList)
const time = new Date().getTime() - startTime
console.log(result)
console.log(time) // 33123

耗费的时间也太多了，一共跑了 33 秒，时间复杂度是 O(n²)，10万长度的排序复杂度就是 O(10000000000)，100 亿。

优化一下，内循环其实没必要进行全部的计算，第一次循环后最后一个数一定是最大的，第二次循环后倒数第二及后面的数一定也是依次排好的，以此类推。那么内循环是不是可以 len - i - 1 ？那就少了一半的计算量。再想想，会不会存在一些数是排好的（不好解释，你自己试一想象一下），那么可以如下优化。

/**
 * 冒泡排序
 * @param {*} list 
 * @returns 返回排序后的数组（也是传进来的数组） 
 */
function bubbleSort(list) {
    const len = list.length
    let stopPoint = len
    for (let i = 0; i < len; i++) {
        let n = 0
        for (let j = 0; j < stopPoint - 1; j++) {
            if (list[j] > list[j+1]) {
                let temp = list[j]
                list[j] = list[j + 1]
                list[j + 1] = temp
                n = j + 1 // j + 1 后面的数字都是有被排序好的，因为没有被替换
            }
        }
        stopPoint = n // 记录下来，下次可以从 n 这里停止比对，n 后面的数是排序好的
    }
    return list
}

看下结果：

const sourceList = []
const len = 100000
for (let i = 0; i < len; i++) {
    // 得到 0 至 len 的随机整数
    let int = Math.floor(Math.random() * (len + 1))
    // 放入数组
    sourceList.push(int)
}
console.log(sourceList)

const startTime = new Date().getTime()
let result = bubbleSort(sourceList)
const time = new Date().getTime() - startTime
console.log(result)
console.log(time) // 17675

是不是快了很多，才 17 秒，大约是只花一半的时间。 不过其实还是不理想。提一下，冒泡排序可以是稳定的，就是说相等的元素不会被打乱顺序。

二分法插入排序

先说插入排序，插入排序就是依次把原数组中的元素逐一放入新数组中，插入的过程是查找插入元素在新数组中的位置，进行插入，也是二次循环，时间复杂度还是 O(n²)，并不会比冒泡排序好。但查找的过程优化一下，用二分查找，那么是不是可以见减少时间复杂度呢？二分查找的复杂度是 O(n(log₂(n))) ，那么二分法插入排序的时间复杂度就是 O(n*log₂(n))，下面看代码：

/**
 * 二分插入排序
 * @param {*} list 
 * @returns 返回排序后新数组
 */
function InsertSort(list) {
    let newList = []
    const len = list.length
    if (len <= 1) {
        return [...list]
    }
    for (let i = 0; i < len; i++) {
        const target = list[i]
        let result = binarySearch(newList, target)
        newList.splice(result, 0, target)
    }
    return newList
}

/**
 * 二分查找
 * @param {*} list 
 * @param {*} target 
 * @returns 返回目标插入索引
 */
function binarySearch(list, target, min, mid, max) {
    const len = list.length
    if (!len) {
        return 0
    }
    if (!mid) {
        mid = Math.floor(len / 2)
        min = 0
        max = len
    }
    let midItem = list[mid]
    if (target < midItem) {
        max = mid
    }
    else {
        min = mid
    }
    mid = Math.floor((max - min) / 2) + min
    if (min === mid) {
        if (target < list[min]) {
            return min
        }
        return mid + 1
    }
    return binarySearch(list, target, min, mid, max)
}

我们看看结果怎么样

const sourceList = []
const len = 100000
for (let i = 0; i < len; i++) {
    // 得到 0 至 len 的随机整数
    let int = Math.floor(Math.random() * (len + 1))
    // 放入数组
    sourceList.push(int)
}
console.log(sourceList)

const startTime = new Date().getTime()
let result = InsertSort(sourceList)
const time = new Date().getTime() - startTime
console.log(result)
console.log(time) // 1122

哇，只需要1.1秒，太快了。很棒！但如果数组长度增加到 1,000,000，那么时间是 158,840ms 约为 158 秒。这样太慢了。

但不怕，我们还有更快的算法。

快速排序

我能理解，但我实在是不会解释，我们看 wikipedia 上的解释：

快速排序（英语：Quicksort），又称分区交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序 n 个项目要 O(n(log₂(n)))（大O符号）次比较。在最坏状况下则需要 O(n²) 次比较，但这种状况并不常见。事实上，快速排序 Θ(n(log₂(n)) 通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。 步骤为： 挑选基准值：从数列中挑出一个元素，称为“基准”（pivot）， 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，

递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。 递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。

选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。

按解释上说，他的平局状况下复杂度也高达 Θ(n(log₂(n))，看着也并不比二分法插入排序更快，但实际情况，它的速度基本上比 O(n(log₂(n))) 算法的速度快，我们看下代码：

/**
 * 快速查找
 * @param {*} list 
 * @returns 返回排序好的新数组
 */
function quickSort(list) {
    let len = list.length
    if (len <= 1) {
        return [...list]
    }
    const pivotIndex = getPivotIndex(len)
    const pivot = list[pivotIndex]
    const left = []
    const right = []
    for (let i = 0; i < len; i++) {
        if (pivotIndex !== i) {
            let item = list[i]
            if (item < pivot) {
                left.push(item)
            }
            else {
                right.push(item)
            }
        }
    }
    let leftResult = quickSort(left)
    let rightResult = quickSort(right)
    return leftResult.concat(pivot).concat(rightResult)
}

// 获取随机基准值的索引
function getPivotIndex(len) {
    const pivot = Math.floor(Math.random() * (len))
    return pivot
}

我们看结果：

const sourceList = []
const len = 100000
for (let i = 0; i < len; i++) {
    // 得到 0 至 len 的随机整数
    let int = Math.floor(Math.random() * (len + 1))
    // 放入数组
    sourceList.push(int)
}
console.log(sourceList)

const startTime = new Date().getTime()
let result = quickSort(sourceList)
const time = new Date().getTime() - startTime
console.log(result)
console.log(time) // 82

10万数组长度时间是 82 毫秒，1秒不到，貌似比二分法插入排序的 1.1 少好了些，但也没有好太多。 我们再看 10倍长度（1,000,000）长度结果会是多少，

const sourceList = []
const len = 1000000
for (let i = 0; i < len; i++) {
    // 得到 0 至 len 的随机整数
    let int = Math.floor(Math.random() * (len + 1))
    // 放入数组
    sourceList.push(int)
}
console.log(sourceList)

const startTime = new Date().getTime()
let result = quickSort(sourceList)
const time = new Date().getTime() - startTime
console.log(result)
console.log(time) // 643

结果是 0.6 秒，比二分法插入排序的 158 秒少好太多了。实际再加 10 倍（10,000,000）长度结果也只是 8 秒左右。 这速度也太快了。

在优化一下。我们看到上面有数组操作，但其实也可以用置换的方法进行排序。注意，这样会更改原数组，不过这应该不是什么问题。

/**
 * 快速排序（原地排序版）
 * @param {*} list 
 * @param {*} left 
 * @param {*} right 
 */
function quickSort (list, left, right) {
    let len = list.length
    if (left === undefined) {
        left = 0
        right = len - 1
    }
    if (left >= right) {
        return list
    }
    pivotIndex = getPivotIndex(left, right)

    pivot = list[pivotIndex]
    swag(list, right, pivotIndex)
    let storeIndex = right - 1
    for (let i = left; i <= storeIndex;) {
        if (i === storeIndex){
            if(list[i] < pivot) {
                storeIndex++
            }
            i++
        }
        else if (list[i] > pivot) {
            swag(list, storeIndex, i)
            storeIndex--
        }
        else {
            i++
        }
    }

    swag(list, right, storeIndex)
    quickSort(list, left, storeIndex - 1)
    quickSort(list, storeIndex + 1, right)
    return list
}

function swag(list, i, j) {
    let temp = list[i]
    list[i] = list[j]
    list[j] = temp
}

function getPivotIndex(left, right) {
    return Math.floor(Math.random() * (right - left + 1) + left)
}

这个方法研究了好久，也没能写得简洁一些，具体原理或更简单的代码网上就有，可以去查找一下。

const sourceList = []
const len = 10000000
for (let i = 0; i < len; i++) {
    // 得到 0 至 len 的随机整数
    let int = Math.floor(Math.random() * (len + 1))
    // 放入数组
    sourceList.push(int)
}
console.log(sourceList)

const startTime = new Date().getTime()
let result = quickSort(sourceList)
const time = new Date().getTime() - startTime
console.log(result)
console.log(time) // 1939

console.log(checkSort(result))

面对 10,000,000 的长度，只用了2秒不到。非常优秀了。

总结

冒泡排序是最基本的排序方法，一般场景也可以用，前端面试很多考官也会问到，但是快排才是上面几个方法中最快的排序法。但快排也有个缺点，不稳定，就是说相等的元素排序后位置可能改变。而二分法插入排序有不错的速度，并且也可是稳定的。所以各有优缺点，也都是基础的排序方法，都学习一下总没错。

附上实验方法的速度比较

各种方法的随机数数组排序花费的时间如下：

方法	10万长度耗时(ms)	100万长度耗时(ms)
冒泡排序	17,037	跑不动
二分法插入排序	1,122	158,840
快速排序	643	8,461
快速排序 (原地排序版)	29	181