『 进阶』用 JS 实现各种数组排序

大家好，我是爱吃鱼的桶哥Z，在前面一节中，我们学习了数组扁平化的 6 种操作方法，今天我们继续来盘一下关于数组中各种排序的实现方法。数组排序是我们在 JavaScript 的编程中经常会遇到的，也是大厂面试中考察的主力点，尤其是调用 sort 方法，下面我们就开始吧！

思考问题

老规矩，我们还是先来思考两个问题，具体如下：

1. 数据结构中稳定的排序算法有哪些？不稳定的排序算法又有哪些？
2. 时间复杂度和空间复杂度分别代表了什么？

带着上述的两个问题，方便我们在学习的过程中时刻回顾我们的学习目标，下面就开始吧！

时间复杂度 & 空间复杂度

在说排序算法前，我们需要先了解一下什么是 时间复杂度，什么是 空间复杂度。

关于 时间复杂度，目前说的比较多的是通过 O(nlogn) 以及 O(n) 来衡量的，其实大多数时候我们对此都并未建立一个形象的认知，因此很多人都分不清到底哪种算法更快，更好。我们可以通过下图来理解关于时间复杂度，如图：

上图中通过不同颜色来区分了最优、一般和最差的算法，其中左边粉红色的表示最差，中间颜色表示一般，最右边的绿色表示最佳，因此我们在日常的开发中，最好能够将一个算法 时间复杂度 维持在 O(nlogn) 以下，要知道一个算法的时间复杂度达到 O(n^2) 就是难以接受的了，因此我们在日常开发中尽量控制不要使用多层循环嵌套，这样可以有效的降低我们算法的 时间复杂度 。

关于 空间复杂度，相对来说就比较容易理解一些了，它主要描述的是一个算法在运行的过程中需要临时占用存储空间大小的度量，有的算法需要占用的临时工作单元数与解决问题的规模有关，如果规模越大，则占用的存储单元越多。

我们了解完 时间复杂度 和 空间复杂度，接下来我们就一起来盘一下各种排序的 JS 实现方法吧！

JavaScript 实现各种排序

数据结构算法中的排序有很多种，根据它们的特性，可以大致分为两种类型：

1. 比较类排序：主要通过比较来决定元素箭的相对次序，其时间复杂度不能突破 O(nlogn)，因此也被称为非线性时间比较类排序；
2. 非比较类排序：主要不通过比较来决定元素间的相对次序，它可以突破基于比较类排序的时间下限，以线性时间运行，因此也被称为线性时间非比较类排序。

我们可以通过一张图来看一下这两种分类方式的区别，如下图：

非比较类的排序在实际的开发中使用较少，因此我们可以着重来看 比较类排序。通过上图中的数据还可以分为稳定排序和非稳定排序，例如：快速排序就是不稳定排序，冒泡排序就是稳定的排序。下面我们一起来看一下各种排序方法的实现。

冒泡排序

冒泡排序 是最基础的排序，一般在最开始学习数据结构的时候就会接触它。冒泡排序 是一次比较两个元素，如果顺序是错误的就把它们交换过来，直到将整个数据列表中的元素都按规定的顺序排好才结束，我们一起来看一下实现代码，如下：

const arr = [1, 3, 5, 3, 2, 18, 26, 1, 33, 92, 157, 48, 9, 762, 128];

const bubbleSort = (arr) => {
    const length = arr.length;
    // 如果数组的长度小于2，表示数组就不需要进行排序，直接返回即可
    if (length < 2) return arr;
    
    // 通过循环来交换两个元素的位置
    for (let i = 0; i < length; i++) {
        for (let j = 0; j < i; j++) {
            // 判断数组中的两个元素大小
            if (arr[j] > arr[i]) {
                // 通过一个临时变量存储较大的值，用于数据的交换
                const temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
    }
    return arr;
};

console.log(bubbleSort(arr));

我们可以看一下在控制台中的执行效果，如下图：

从上图中可以看出，最后返回的数据是已经排好序的结果，关于 冒泡排序 的更多内容，可以在这里进行查看。

快速排序

快速排序 一般通过一趟排序，将待排记录分隔成独立的两个部分，其中一部分记录的关键字均比另外一部分的关键字小，就可以分别对这两部分记录继续进行排序，直到整个序列变成有序的序列。我们一起来看一下实现代码，如下：

const arr = [1, 3, 5, 3, 2, 18, 26, 1, 33, 92, 157, 48, 9, 762, 128];

const quickSort = (arr) => {
    // 内部定义一个快排函数
    const quick = (array) => {
        if (array.length <= 1) return array;
        const len = array.length;
        const index = Math.floor(len >> 1);
        const prev = array.splice(index, 1)[0];
        const left = [];
        const right = [];
        for (let i = 0; i < len; i++) {
            if (array[i] > prev) {
                right.push(array[i]);
            } else if (array[i] <= prev) {
                left.push(array[i]);
            }
        }
        return quick(left).concat([prev], quick(right));
    };
    const result = quick(arr);
    return result;
};

console.log(quickSort(arr));

我们可以在浏览器的控制台中看到上面代码的输出，如图：

上述代码的思路主要是从数组中挑出一个元素，也就是基准，然后重新排序数列，所有元素比基准数值小的，放在基准前面；比基准值大的，放在基准后面。这个区分搞定后，该基准就处于数列的中间位置，然后把小于基准元素的子数列和大于基准元素的子数列递归的调用 quick 方法，以达到快速排序。

插入排序

插入排序 算法描述的是一种简单直观的排序算法，它的工作原理是通过构建有序序列。对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入，从而达到排序的效果。我们一起来看一下代码实现，如下：

const arr = [1, 3, 5, 3, 2, 18, 26, 1, 33, 92, 157, 48, 9, 762, 128];

const insertSort = (arr) => {
    const len = arr.length;
    let current, prev;
    
    for (let i = 1; i < len; i++) {
        current = arr[i];
        prev = i - 1;
        
        while (prev >= 0 && arr[prev] > current) {
            arr[prev + 1] = arr[prev];
            prev--;
        }
        arr[prev + 1] = current;
    }
    return arr;
};

console.log(insertSort(arr));

我们可以在浏览器的控制台中看到上面代码的输出，如图：

从执行的结果中可以发现，通过 插入排序 这种方式实现的排序效果，插入排序的思路是基于数组本身进行调整的。首先遍历数组从 i=1 开始，拿到当前的 current 值，去和前面的值进行比较，如果前面的值大于当前的值，就把前面的值和当前的值进行交换。通过这样不断循环往复，最终达到排序的目的。

选择排序

选择排序 是一种简单直观的排序算法，它的工作原理是，首先将最小的元素存放在序列的起始位置，然后再从剩余未排序的元素中继续寻找最小元素，最后再放到已排序的序列后面。通过这样不断的重复执行，直到所有的元素均排序完毕。我们一起来看一下代码实现，如下：

const arr = [1, 3, 5, 3, 2, 18, 26, 1, 33, 92, 157, 48, 9, 762, 128];

const selectSort = (arr) => {
    const len = arr.length;
    let temp, minIndex;
    
    for (let i = 0; i < len - 1; i++) {
        minIndex = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[j] <= arr[minIndex]) {
                minIndex = j
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
};

console.log(selectSort(arr));

我们可以在浏览器的控制台中看到上面代码的输出，如图：

从上述的代码中可以看到，这个排序算法是表现的稳定的排序算法之一，因为无论什么样的数据进去都是 O(n^2) 的时间复杂度，因此用到这个算法的时候，数据规模越小越好。

堆排序

堆排序 是指利用堆这种数据结构所设计的一种排序算法。堆 其实是一个近似完全二叉树的结构，并同时满足堆的性质，也就是子节点的键值或索引总是小于(或者大于)它的父节点。堆的底层 实际上就是一颗完全二叉树，可以用数组来实现。我们一起来看一下代码实现，如下：

const arr = [1, 3, 5, 3, 2, 18, 26, 1, 33, 92, 157, 48, 9, 762, 128];

const heapSort = (arr) => {
    const len = arr.length;
    let k = 0;
    
    function swap (i, j) {
        let temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    function maxHeapify (start, end) {
        let dad = start;
        let son = dad * 2 + 1;
        if (son >= end) return;
        if (son + 1 < end && arr[son] < arr[son + 1]) {
            son++;
        }
        if (arr[dad] <= arr[son]) {
            swap(dad, son);
            maxHeapify(son, end);
        }
    }
    
    for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
        maxHeapify(i, len);
    }
    
    for (let j = len - 1; j > k; j--) {
        swap(0, j);
        maxHeapify(0, j);
    }
    
    return arr;
};

console.log(heapSort(arr));

我们可以在浏览器的控制台中看到上面代码的输出，如图：

通过上述的代码可以看出，堆排序 整体会比其它的排序复杂一些，理解起来也相对困难一些。我们只需要注意两点：

1. 堆排序最核心的点在于排序前先建堆；
2. 由于堆就是一个完全二叉树，如果父节点的序号为 N ，子节点的需要就分别是 2N 和 2N + 1。

只有理解上述这两点，再来看代码相对来说就比较容易理解了。

归并排序

归并排序 是建立在归并操作上的一种有效的排序算法，该算法是采用 分治法 的一个非常典型的应用，把已有序的子序列合并，得到完全有序的序列，先使每个子序列有序，然后再使子序列间断有序。如果将两个有序列表合并成一个有序列表，则称为二路归并。我们一起来看一下代码实现，如下：

const arr = [1, 3, 5, 3, 2, 18, 26, 1, 33, 92, 157, 48, 9, 762, 128];

function mergeSort (arr) {
    const merge = (right, left) => {
        const result = [];
        let il = 0, ir = 0;
        
        while (il < left.length && ir < right.length) {
            if (left[il] < right[ir]) {
                result.push(left[il++]);
            } else {
                result.push(right[ir++]);
            }
        }
        
        while (il < left.length) {
            result.push(left[il++]);
        }
        
        while (ir < right.length) {
            result.push(right[ir++]);
        }
        
        return result;
    };
    
    const mergeSort = array => {
        if (array.length === 1) { return array };
        const mid = Math.floor(array.length / 2);
        const left = array.slice(0, mid);
        const right = array.slice(mid, array.length);
        return merge(mergeSort(left), mergeSort(right));
    };
    
    return mergeSort(arr);
};

console.log(mergeSort(arr));

我们可以在浏览器的控制台中看到上面代码的输出，如图：

上述代码可以看到，通过归并排序就可以得到想要的结果。在归并排序中，使用递归调用两个数组进行排序，最终得出结果。

归并排序是一种稳定的排序方法，它的性能不受输入数据的影响，但它的表现比选择排序要好的多，而代价是需要额外的内存空间。对前端来说，用空间换时间反而是我们更愿意的。

最后

通过这一节内容的讲解，介绍了6中不同的排序算法，最简单也是最基础的 冒泡排序 是大家都需要掌握的，但它的计算效率是最低的。而 归并排序 的时间复杂度是最低的，效率相对来说也是最高的，因此还是有必要掌握的。

最开始的两个问题，现在应该已经有答案了吧？

最后，如果这篇文章有帮助到你，❤️关注+点赞❤️鼓励一下作者，谢谢大家

往期回顾

『 纯干货』帮你梳理总结眼花缭乱的数组 API

如何实现 new、apply、call、bind ？这篇文章告诉你

JS 中这些继承方式你知道吗？

箭头函数能作为事件监听的回调函数吗？

用操作数组的方式来操作对象，该怎么做？

这几个数组的操作方法你必须知道

JS 中的类数组，是时候了解了