{T}

数组排序是编程中的高频场景，也是面试考察的重点。本文先从时间复杂度和空间复杂度入手，再用 JavaScript 实现六种常见的比较类排序算法。

时间复杂度 & 空间复杂度

时间复杂度：衡量算法运行时间随数据规模增长的速率，常用大 O 表示，如 O(n)、O(nlogn)、O(n²)。编写代码时应尽量将时间复杂度维持在 O(nlogn) 以下，超过 n² 的复杂度通常难以接受。

空间复杂度：衡量算法在运行过程中临时占用的存储空间大小。有的算法需要的临时工作单元数与问题规模相关，例如归并排序和快速排序的空间复杂度就不同。

排序算法可大致分为两类：

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

非比较类排序在实际中较少使用，本文主要介绍比较类排序。此外根据排序的稳定性，又可分为稳定排序（如冒泡排序）和不稳定排序（如快速排序）。

冒泡排序

冒泡排序是最基础的排序，依次比较相邻两个元素，顺序错误就交换，重复走访直到不再需要交换。

javascript
var a = [1, 3, 6, 3, 23, 76, 1, 34, 222, 6, 456, 221];
function bubbleSort(array) {
  const len = array.length;
  if (len < 2) return array;
  for (let i = 0; i < len; 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;
}
bubbleSort(a); // [1, 1, 3, 3, 6, 6, 23, 34, 76, 221, 222, 456]

快速排序

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分的关键字均比另一部分小，再分别对两部分递归排序，使整个序列有序。

javascript
var a = [1, 3, 6, 3, 23, 76, 1, 34, 222, 6, 456, 221];
function quickSort(array) {
  var quick = function(arr) {
    if (arr.length <= 1) return arr;
    const index = Math.floor(arr.length >> 1);   // 取中间下标
    const pivot = arr.splice(index, 1)[0];       // 基准值
    const left = [];
    const right = [];
    for (let i = 0; i < arr.length; 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));
  };
  return quick(array);
}
quickSort(a); // [1, 1, 3, 3, 6, 6, 23, 34, 76, 221, 222, 456]

思路：从数列中挑出一个元素作为「基准」（pivot），把所有比基准小的元素放在基准前面、比基准大的放在后面，该基准就处于数列中间位置，然后对左右子数列递归调用 quick 排序。

插入排序

插入排序通过构建有序序列，对未排序数据在已排序序列中从后向前扫描，找到合适位置插入。

javascript
var a = [1, 3, 6, 3, 23, 76, 1, 34, 222, 6, 456, 221];
function insertSort(array) {
  const len = array.length;
  let current;
  let prev;
  for (let i = 1; 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;
}
insertSort(a); // [1, 1, 3, 3, 6, 6, 23, 34, 76, 221, 222, 456]

思路：从 i = 1 开始，取当前值 current 与前面已排序的元素比较，若前面的值更大则后移，直到找到正确位置插入。

选择排序

选择排序将最小的元素放到序列起始位置，再从剩余未排序元素中继续寻找最小元素放到已排序序列后面，依此类推。

javascript
var a = [1, 3, 6, 3, 23, 76, 1, 34, 222, 6, 456, 221];
function 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;
}
selectSort(a); // [1, 1, 3, 3, 6, 6, 23, 34, 76, 221, 222, 456]

选择排序是最稳定的排序算法之一，无论什么数据都是 O(n²) 的时间复杂度，数据规模越小越合适。

堆排序

堆排序利用堆这种数据结构设计排序算法。堆是一个近似完全二叉树的结构，且满足父节点的键值总是不小于（或不大于）子节点的性质。堆的底层实际上就是一棵可用数组实现的完全二叉树。

javascript
var a = [1, 3, 6, 3, 23, 76, 1, 34, 222, 6, 456, 221];
function heap_sort(arr) {
  var len = arr.length;
  function swap(i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  function max_heapify(start, end) {
    var dad = start;
    var 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 (var i = Math.floor(len / 2) - 1; i >= 0; i--) {
    max_heapify(i, len);
  }
  // 逐步将堆顶最大值交换到末尾
  for (var j = len - 1; j > 0; j--) {
    swap(0, j);
    max_heapify(0, j);
  }
  return arr;
}
heap_sort(a); // [1, 1, 3, 3, 6, 6, 23, 34, 76, 221, 222, 456]

堆排序的核心两点：一是排序前先建堆；二是堆是完全二叉树，若父节点序号为 n，则叶子节点序号分别为 2n 和 2n+1。两个循环分别处理父节点顺序和堆的调整。

归并排序

归并排序是建立在归并操作上、采用分治法的一种典型算法。将已有序的子序列合并，得到完全有序的序列；先使每个子序列有序，再使子序列段间有序。

javascript
var a = [1, 3, 6, 3, 23, 76, 1, 34, 222, 6, 456, 221];
function mergeSort(array) {
  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 sort = (arr) => {
    if (arr.length === 1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid, arr.length);
    return merge(sort(left), sort(right));
  };
  return sort(array);
}
mergeSort(a); // [1, 1, 3, 3, 6, 6, 23, 34, 76, 221, 222, 456]

从 sort 方法可以看到，通过 mid 把数组分成左右两部分，分别递归排序后，再将两个有序数组按顺序归并。归并排序是稳定的，性能不受输入数据影响，始终是 O(nlogn) 的时间复杂度，代价是需要额外的内存空间。

复杂度对比

排序算法平均时间复杂度空间复杂度稳定性
冒泡排序O(n²)O(1)稳定
快速排序O(nlogn)O(logn)不稳定
插入排序O(n²)O(1)稳定
选择排序O(n²)O(1)不稳定
堆排序O(nlogn)O(1)不稳定
归并排序O(nlogn)O(n)稳定

总结

本文介绍了六种常见排序算法的 JavaScript 实现，并整理了它们的复杂度与稳定性对比。实际需要自己实现排序时，可根据空间和时间复杂度综合考量，选择最适合的排序方法。例如数据量小时可用插入排序，需要稳定排序且不介意空间开销时可用归并排序。