[数据结构与算法]如何用 JS 实现各种数组排序？

如何用 JS 实现各种数组排序

??数组排序是在 JavaScript的编程过程中经常会遇到的，也是面试中会考察的，尤其是调用 sort方法，不过今天主要围绕数据结构排队进行讲解，关于 sort方法的详细剖析会在下一讲探讨。

为了方便更好地理解本讲的内容，在开始前请先思考几个问题。

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

时间复杂度&空间复杂度

??在说排序算法之前，需要重新了解一下时间复杂度和空间复杂度。

??关于时间复杂度，我们说的更多的是通过 O(nlogn) 以及 O(n)等来衡量。其实大多数时候对此并未建立形象的认知，到底哪一种算法更快、更好呢？下面是一张时间复杂度的曲线图，方便理解。

??图中用颜色区分了最优的、一般的以及比较差的时间复杂度，可以看到有这几种分类：Excellent、Good、Fair、Bad、Horrible，通过这张图可以一目了然。因此你在面试或者日常工作中编写代码的时候，要努力将代码的时间复杂度维持在 O(nlogn) 以下，要知道凡是超过 n 平方的时间复杂度都是难以接受的。

??空间复杂度比较容易理解，就是对一个算法在运行过程中临时占用存储空间大小的度量。有的算法需要占用的临时工作单元数与解决问题的规模有关，如果规模越大，则占的存储单元越多。比如，归并排序和快速排序的空间复杂度就是不太一样的。

各种排序的 JS 实现

??数据结构算法中排序有很多种，常见的、不常见的，至少包含十种以上。根据它们的特性，可以大致分为两种类型：比较类排序和非比较类排序。

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

??通过一张图片来看看这两种分类方式分别包括哪些排序方法。

??非比较类的排序在实际情况中用的比较少，主要围绕比较类排序展开讲解。其实根据排序的稳定性，也可以分为稳定排序和不稳定排序，例如快速排序就是不稳定的排序、冒泡排序就是稳定的排序。

冒泡排序

??冒泡排序是最基础的排序，一般在最开始学习数据结构的时候就会接触它。冒泡排序是一次比较两个元素，如果顺序是错误的就把它们交换过来。走访数列的工作会重复地进行，直到不需要再交换，也就是说该数列已经排序完成。请看下面的代码。

  const a = [1, 3, 6, 23, 45, 56, 5, 7, 1, 234, 444, 565, 2];
  const bubbleSort = (array) => {
    const length = array.length;
    if (length < 2) {
      return array;
    }
    for (let i = 0; i < length; i++) {
      for (let j = 0;j<i;j++) {
        if (array[j] > array[i]) {
          const temp = array[j];
          array[j] = array[i];
          array[i] = temp;
        }
      }
    }
    return array;
  };
  console.log(bubbleSort(a)); // (13) [1, 1, 2, 3, 5, 6, 7, 23, 45, 56, 234, 444, 565]

??从上面这段代码可以看出，最后返回的是排好序的结果。因为冒泡排序实在太基础和简单，这里就不过多赘述了。

快速排序

??快速排序的基本思想是通过一趟排序，将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序。

const a = [1, 3, 6, 23, 45, 56, 5, 7, 1, 234, 444, 565, 2];
  const quickSort = (array) => {
    const quick = function (arr) {
      const len = arr.length;
      if (len <= 1) {
        return arr;
      }

      const index = Math.floor(len >> 1);

      const pivot = arr.splice(index, 1)[0];

      const left = [];

      const right = [];

      for (let i = 0; i < len; i++) {
        if (arr[i] > pivot) {
          right.push(arr[i]);
        } else if (arr[i] <= pivot) {
          left.push(arr[i]);
        }
      }

      return quick(left).concat([pivot], quick(right));
    };

    const result = quick(array);

    return result;
  };

  console.log(quickSort(a)); // (13) [1, 1, 2, 3, 5, 6, 7, 23, 45, 56, 234, 444, 565]

??上面的代码在控制台执行之后，也可以得到预期的结果。最主要的思路是从数列中挑出一个元素，称为 “基准”（pivot）；然后重新排序数列，所有元素比基准值小的摆放在基准前面、比基准值大的摆在基准的后面；在这个区分搞定之后，该基准就处于数列的中间位置；然后把小于基准值元素的子数列（left）和大于基准值元素的子数列（right）递归地调用 quick方法排序完成，这就是快排的思路。

插入排序

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

  const a = [1, 3, 6, 23, 45, 56, 5, 7, 1, 234, 444, 565, 2];
  const insertSort = (array) => {
    const len = array.length;
    let current;
    let prev;
    for (let i = 0; i < len; i++) {
      current = array[i];
      prev = i - 1;
      while (prev >= 0 && array[prev] > current) {
        array[prev + 1] = array[prev];
        prev--;
      }
      array[prev + 1] = current;
    }
    return array;
  };

  console.log(insertSort(a)); // (13) [1, 1, 2, 3, 5, 6, 7, 23, 45, 56, 234, 444, 565]

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

选择排序

??选择排序是一种简单直观的排序算法。它的工作原理是，首先将最小的元素存放在序列的起始位置，再从剩余未排序元素中继续寻找最小元素，然后放到已排序的序列后面……以此类推，直到所有元素均排序完毕。请看下面的代码。

const a = [1, 3, 6, 23, 45, 56, 5, 7, 1, 234, 444, 565, 2];
  const selectSort = (array) => {
    const len = array.length;
    let temp;
    let minIndex;
    for (let i = 0; i < len - 1; i++) {
      minIndex = i;
      for (let j = i + 1; j < len; j++) {
        if (array[j] <= array[minIndex]) {
          minIndex = j;
        }
      }
      temp = array[i];
      array[i] = array[minIndex];
      array[minIndex] = temp;
    }
    return array;
  };
  console.log(selectSort(a)); // (13) [1, 1, 2, 3, 5, 6, 7, 23, 45, 56, 234, 444, 565]

??这样，通过选择排序的方法同样也可以实现数组的排序，从上面的代码中可以看出该排序是表现最稳定的排序算法之一，因为无论什么数据进去都是 O(n 平方)的时间复杂度，所以用到它的时候，数据规模越小越好。

堆排序

??堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质，即子结点的键值或索引总是小于（或者大于）它的父节点。堆的底层实际上就是一棵完全二叉树，可以用数组实现。

??根节点最大的堆叫作大根堆，根节点最小的堆叫作小根堆，你可以根据从大到小排序或者从小到大来排序，分别建立对应的堆就可以。请看下面的代码。

  const a = [1, 3, 6, 23, 45, 56, 5, 7, 1, 234, 444, 565, 2]; 
  const heap_sort= (arr)=>{
    let len = arr.length;
    let k = 0;
    const swap = (i,j)=>{
      let temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    } 
    const max_heapify = (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);
        max_heapify(son,end);
      } 
    }
    for (let i = Math.floor(len/2)-1;i>=0;i--) {
      max_heapify(i,len);
    }
    for (let j = len-1;j>k;j--) {
      swap(0,j);
      max_heapify(0,j)
    }
    return arr;
  }
  console.log(heap_sort(a)); // (13) [1, 1, 2, 3, 5, 6, 7, 23, 45, 56, 234, 444, 565]

??从代码来看，堆排序相比上面几种排序整体上会复杂一些，不太容易理解。不过你应该知道两点：一是堆排序最核心的点就在于排序前先建堆；二是由于堆其实就是完全二叉树，如果父节点的序号为n，那么叶子节点的序号就分别是 2n 和 2n+1。

??理解了这两点，再看代码就比较好理解了。堆排序最后有两个循环：第一个是处理父节点的顺序；第二个循环则是根据父节点和叶子节点的大小对比，进行堆的调整。通过这两轮循环的调整，最后堆排序完成。

归并排序

??归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。我们先看一下代码。

const a = [1, 3, 6, 23, 45, 56, 5, 7, 1, 234, 444, 565, 2];
  const mergeSort = (arr) => {
    const merge = (right, left) => {
      const result = [];
      let il = 0;
      let 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(a)); // (13) [1, 1, 2, 3, 5, 6, 7, 23, 45, 56, 234, 444, 565]

??从上面这段代码中可以看到，通过归并排序可以得到想要的结果。上面提到了分治的思路，你可以从 mergeSort方法中看到，通过 mid可以把该数组分成左右两个数组，分别对这两个进行递归调用排序方法，最后将两个数组按照顺序归并起来。

??归并排序是一种稳定的排序方法，和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好得多，因为始终都是 O(nlogn) 的时间复杂度。而代价是需要额外的内存空间。

总结

??以下表格汇总了它们各自的时间复杂度和空间复杂度：

??其中可以看到排序相关的时间复杂度和空间复杂度以及稳定性的情况，如果遇到需要自己实现排序的时候，可以根据它们的空间和时间复杂度综合考量，选择最适合的排序方法。