在实现过程中，参考了许多大佬的博客，不能全部列出，在此致谢，致歉。

本文不讲基础的原理过程，只贴JavaScript代码，供想使用JavaScript实现排序的读者参考。

排序的方法很重要，不同的排序方法效率差距还是很大的。打开控制台即可测试不同排序方法的效率如何。

// 我们用下面的方法测试函数执行时间
console.time("name"); // 开始计时
function(){}; // 你的函数
console.timeEnd("name"); // 结束计时

1. 冒泡排序

冒泡排序是最经典的排序方法。两两比较，每一轮找出一个最大的值，沉入最底。

function bubble(array){
    for(let i = 0; i < array.length - 1; i ++){
        for(let j = 0; j < array.length - 1 - i; j ++){
            if(array[j] > array[j + 1]){
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

改进版的冒泡，在没有可交换的操作时，提前结束。

// 改进冒泡,任何一轮没有可交换的操作时，结束
function bubble(array){
    for(let i = 0; i < array.length - 1; i ++){
        console.log("------第" + i + "轮------")
        let flag = 0;
        for(let j = 0; j < array.length - 1 - i; j ++){
            if(array[j] > array[j + 1]){
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                flag ++;
            }
        }
        if(flag === 0){
            break;
        }
    }
}

2. 选择排序法

选择排序，每次选择最小值。

function selection(a){
    for(let i = 0; i < a.length; i++){
        // 在剩余的元素中选择最小值
        let min = i;
        for(let j = i+1; j < a.length; j++){
            if(a[j] < a[min]){
                min = j;
            }
        }
        // 交换
        let temp = a[i];
        a[i] = a[min];
        a[min] = temp;
    }
}

3. 插入排序法

插入排序将序列分成两组，一组已排序一组未排序，每次从未排序的之中拉一个到已排序的中，选择合适的位置***去，故叫插入法。但一般用数组实现时，没有直接的插入方法，故实际上我们使用的还是两两对比交换位置的方法实现插入。在由小到大排序时，我们经常从后往前判断插入位置。

// 最终的结果看起来是前插，实际上实现过程我们依然用的是交换
// 不停地交换，直到到达合适的位置，即看起来像是直接插到合适的位置。
function _insertion(a){
    for(let i = 1; i < a.length; i ++){
        let j = i; // i 代表现在是第几轮
        console.log("------第" + j + "轮------")
        while(j > 0 && a[j] < a[j - 1]){
            let temp = a[j - 1];
            a[j - 1] = a[j];
            a[j] = temp; // 前插
            j --;
        }
        console.log(a);
    }
}

使用for循环实现：

// 插入
// i 是排序与未排序的分水岭,i从1移动到最后,已排序的吃掉所有未排序的
// i及以后是未排序的,i以前是已经排序的
function insertion(arr) {
	for (let i = 1; i < arr.length; i++) { // 未排序
		for (let j = i - 1; j >= 0; j--) { // 已排序,从后往前插入
			if (arr[j + 1] < arr[j]) {
				// 小了交换位置,往前移
				swap(j, j + 1, arr)
			} else {
				// 大了结束
				break;
			}
		}
	}
}

另一种思路：把交换拆成两个步骤，先挖坑但不着急填坑，直到找到最后欲插入位置再结束循环填坑。

// 插入
function insertion(arr) {
	for (let i = 1; i < arr.length; i++) { // i 就是想要插入到已排序的那组当中去的当前值
		let currentWaitingToInsert = arr[i];
		let j = 0; // 记录欲插入位置
		for (j = i - 1; j >= 0; j--) { // j 依次遍历已排序的那组,从后往前,即从大到小
			if (currentWaitingToInsert < arr[j]) {
				arr[j + 1] = arr[j]; // 后移欲插入位置上的原有数据
			} else {
				// 找到了欲插入位置
				break;
			}
		}
		arr[j + 1] = currentWaitingToInsert; // 插入
	}
}

4. 希尔排序

用一个gap打乱基本插入法的顺序，先进行粗排，减少交换次数，提升效率。

// shell排序法,缩小增量排序,减少数据搬移的次数
function shell(a){
    let n = a.length;
    let gap = n;
    do{
        gap = gap % 2 === 0 ? gap / 2 : (gap - 1) / 2; // 向下取整(c语言里直接int)
        for(let i = gap; i < n; i ++){ // 从gap到length
            let j = i;
            while(j - gap >= 0 && a[j] < a[j - gap]){
                let temp = a[j - gap];
                a[j - gap] = a[j];
                a[j] = temp; // 前插
                j -= gap;
            }
        }
    }while(gap > 1)
}

5. 快速排序

快速排序网上大概有三种方法：挖坑法、左右指针法、前后指针法。

挖坑法。挖新坑，用新坑的土填旧坑。

// 快速排序
// 挖坑法
function quick(a, l, r){
    if(r > l){ // 截止条件，左右相逢
        let _i = l;
        let _j = r;
        let key = a[_i]; // 挖坑
        while(_i < _j){ // 萍水未相逢， 只有相逢才是出路
            while(_i < _j && a[_j] >= key){ // 未相逢，位正前移
                _j --;
            } // 相逢 或 位不正
            if(_i < _j){ // 确认是位不正
                a[_i] = a[_j]; // 填旧坑，挖新坑
            }
            while(_i < _j && a[_i] <= key){
                _i ++;
            }
            if(_i < _j){
                a[_j] = a[_i];
            }
        }
        a[_i] = key;
        quick(a, l, _i - 1);
        quick(a, _i + 1, r);
    }
}

左右指针法。左右交换。

// 左右指针法
function quick(array, left, right){
    if(left < right){
        let i = left;
        let j = right;
        let key = array[i];
        while(i !== j){
            while(i < j && array[j] >= key){
                --j;
            }
            while(i < j && array[i] <= key){
                ++i;
            }
            if(i < j){
                swap(i, j);
            }
        }
        swap(left, i);
        quick(array, left, i - 1);
        quick(array, i + 1, right);
    }

    function swap(x, y){
        let temp = array[x];
        array[x] = array[y];
        array[y] = temp;
    }
}

前后指针法。这个路子比较野，不好理解。

// 前后指针法
function quick(array, left, right){
    if(left < right){
        let cur = left;
        let pre = left - 1;
        let mid = getMid();
        let key = array[mid];
        swap(mid, right); // 将基准值放在最右
        while(cur < right){
            while(array[cur] < key && ++pre !== cur){
                swap(pre, cur);
            }
            ++cur;
        }
        swap(++pre, cur);

        quick(array, left, pre - 1);
        quick(array, pre + 1, right);
    }

    // 三数取中法
    function getMid(){
        let mid = (right - left) % 2 === 0 ? left + (right - left) / 2 : left + (right - left - 1) / 2;
        if(array[mid] > array[left]){
            if(array[mid] < array[right]){
                return mid;
            }else if(array[right] > array[left]){
                return right;
            }else{
                return left;
            }
        }else{
            if(array[mid] > array[right]){
                return mid;
            }else if(array[right] > array[left]){
                return left;
            }else{
                return right;
            }
        }
    }
    function swap(x, y){
        let temp = array[x];
        array[x] = array[y];
        array[y] = temp;
    }
}

6. 堆排序

大根堆（大顶堆）是一颗完全二叉树，树的每一个节点的值要大于他的左右孩子的值。

// 大根堆
function heap_big(array){
    function heap(array, parent, length){
        let temp = array[parent]; // 把老子挂起来
        let child = 2 * parent + 1;
        while(child < length){
            // 选出最能干的儿子
            if(child + 1 < length && array[child + 1] > array[child]){
                child = child + 1;
            }
            // 老子还是比儿子能干，老子继续干
            if(array[parent] > array[child]){
                break;
            }
            // 儿子比老子能干,子代父
            array[parent] = array[child];
            array[child] = temp;
            // 更新，循环
            parent = child;
            child = 2 * parent + 1;
        }
    }
    // Math.floor(array.length/2)是第一个叶子结点，减一就是非叶子节点
    for(let i = Math.floor(array.length / 2) - 1; i > 0; i--){
        // 由下至上的针对每一个非叶子节点调整
        heap(array, i, array.length);
    }
    return array;
}

大根堆排序法。大根堆的根节点必然是序列中的最大值，所以每次求得序列最大值，最后挖去最大值再生成大根堆。

// 大根堆排序
function heap_big(array){
    function heap(array, parent, length){
        let temp = array[parent]; // 把老子挂起来
        let child = 2 * parent + 1;
        while(child < length){
            // 选出最能干的儿子
            if(child + 1 < length && array[child + 1] > array[child]){
                child = child + 1;
            }
            // 老子还是比儿子能干，老子继续干
            if(array[parent] > array[child]){
                break;
            }
            // 儿子比老子能干,子代父
            array[parent] = array[child];
            array[child] = temp;
            // 更新，循环
            parent = child;
            child = 2 * parent + 1;
        }
    }
    // 初始化
    for(let i = Math.floor(array.length / 2) - 1; i > 0; i--){
        // 由下至上的针对每一个非叶子节点调整
        heap(array, i, array.length);
    }
    for(let j = array.length - 1; j > 0; j--){
        // 交换
        let temp = array[0];
        array[0] = array[j];
        array[j] = temp;
        // 对根节点 调整
        heap(array, 0, j);
    }
}

7. 基数排序法

基数排序法属于分配排序（distribution sort），又称桶子法（bucket sort）。通过装桶倒桶排序。

// 基数排序法
function radixSort(array){
    function getDigit(num, radix){
        let result = (num % (radix * 10) - num % radix) / radix;
        return result;
    }
    let bucket = []; // 桶
    let flag = true; // 是否继续
    function initBucket(){
        for(let i = 0; i < 10; i++){
            bucket[i] = []; // 空桶
        }
    }
    initBucket();
    while(flag){
        flag = false;
        let radix = 10 ** i;
        // 根据基数填进桶里
        for(let i = 0; i < array.length; i ++){
            let index = getDigit(array[i], radix);
            if(index !== 0){
                flag = true;
            }
            bucket[index].push(array[i]);
        }
        // 桶里倒出来
        let k = 0;
        for(let i = 0; i < 10; i ++){
            for(let j = 0; j < bucket[i].length; j ++){
                array[k] = bucket[i][j];
                k++;
            }
        }
        // 清空桶
        initBucket();
        // 更新基数
        i ++;
    }
}