创见博客
主流排序算法：JS 实现、时间复杂度与空间复杂度
七崽爱吃小饼干2026/09/16阅读 0

面试里问排序，真正想看的不是你能不能背出 O(n log n)，而是三件事：你能不能手写出来、你清不清楚它在最坏情况下会不会退化、你知不知道它稳不稳定。

先看一个最容易被忽略的事实：同一个数组 [5, 3, 8, 1, 9, 2]，不同算法排完结果一样，但过程的代价差得很远。比如数据已经基本有序时，插入排序只要 O(n)，而选择排序雷打不动 O(n²)——它根本不关心数据长什么样。

这篇文章按"从暴力到线性"的顺序，把主流排序算法一次讲清，每个都给可直接跑的 JS 实现，并附上复杂度、稳定性和适用场景。

一、先明确两个评价维度

时间复杂度：分最好、平均、最坏三种。真正决定工程风险的是最坏情况——快排平均 O(n log n)，但最坏 O(n²)，这就是为什么很多语言的内置排序不敢裸用它。

空间复杂度：算法执行时额外占用的内存（不含原数组）。O(1) 叫"原地排序"，O(n) 叫"非原地"。

还有一个常被追问的维度：

稳定性：值相等的两个元素，排序后相对顺序是否保持不变。

  • 稳定：冒泡、插入、归并、计数、桶、基数。
  • 不稳定：选择、希尔、快排、堆排。

为什么稳定重要？举个真实例子：一张订单表已经按时间排好，现在要"按金额排序，金额相同的保持时间顺序"。此时就必须用稳定排序，否则时间顺序会被打乱，得重新按金额、时间双字段排。

二、O(n²) 三兄弟：冒泡、选择、插入

这三个是入门，但面试常用来考察你对"最好/最坏"的理解。

1. 冒泡排序（Bubble Sort）

相邻两两比较，大的往后冒。加一个 swapped 标志，某轮没有交换就说明已经有序，可以直接结束。

js
function bubbleSort(arr) {
  const a = arr.slice();
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    // 每一轮结束，末尾 i 个元素已经就位，所以内层可以少跑 i 次
    for (let j = 0; j < n - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // 已经有序，提前退出
  }
  return a;
}
  • 最好 O(n)（已有序 + 标志位），平均/最坏 O(n²)。
  • 空间 O(1)，稳定。

2. 选择排序（Selection Sort）

每一轮从未排序区间里找最小值，和区间头部交换。

js
function selectionSort(arr) {
  const a = arr.slice();
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < n; j++) {
      if (a[j] < a[minIndex]) minIndex = j;
    }
    if (minIndex !== i) [a[i], a[minIndex]] = [a[minIndex], a[i]];
  }
  return a;
}
  • 最好/平均/最坏都是 O(n²)——它不感知数据是否有序。
  • 空间 O(1)，不稳定（交换会跨过相等元素）。
  • 优点：交换次数最少，最多 n-1 次，适合"移动成本很高"的场景。

3. 插入排序（Insertion Sort）

像打扑克理牌：把当前元素插入到前面已排好序的正确位置。

js
function insertionSort(arr) {
  const a = arr.slice();
  for (let i = 1; i < a.length; i++) {
    const cur = a[i];
    let j = i - 1;
    while (j >= 0 && a[j] > cur) {
      a[j + 1] = a[j]; // 元素后移
      j--;
    }
    a[j + 1] = cur;
  }
  return a;
}
  • 最好 O(n)（已有序），平均/最坏 O(n²)。
  • 空间 O(1)，稳定。
  • 关键价值：小数组或基本有序时非常快。这就是为什么 TimSort、快排的底层递归到小数组时会切换到插入排序。

三兄弟对比：

算法最好平均最坏空间稳定
冒泡O(n)O(n²)O(n²)O(1)是
选择O(n²)O(n²)O(n²)O(1)否
插入O(n)O(n²)O(n²)O(1)是

三、希尔排序：插入排序的"分步长"升级

插入排序的短板是每次只能把元素往前挪一格。希尔排序的思路是：先用大步长把数组变得"大致有序"，再逐步缩小步长，最后用步长 1 做一次插入排序。 因为前面已经粗排过，最后一次插入排序的移动量很小。

js
function shellSort(arr) {
  const a = arr.slice();
  const n = a.length;
  // 经典的 Knuth 增量序列：1, 4, 13, 40 ...
  let gap = 1;
  while (gap < n / 3) gap = gap * 3 + 1;

  for (; gap >= 1; gap = Math.floor(gap / 3)) {
    for (let i = gap; i < n; i++) {
      const cur = a[i];
      let j = i - gap;
      while (j >= 0 && a[j] > cur) {
        a[j + gap] = a[j];
        j -= gap;
      }
      a[j + gap] = cur;
    }
  }
  return a;
}
  • 复杂度取决于增量序列。Knuth 序列约为 O(n^1.5)；最坏可退化到 O(n²)（如 Shell 原始序列）。
  • 空间 O(1)，不稳定（跨 gap 的交换会打乱相等元素顺序）。
  • 它是第一个突破 O(n²) 的算法，理解它有助于理解快排的分组思想。

四、分治双雄：归并排序与快速排序

这两个是平均 O(n log n) 的主力，也是面试手写重点。

1. 归并排序（Merge Sort）

思路：不断对半切分，直到每段只剩一个元素（天然有序），再两两合并。 合并两个有序数组是它的核心操作。

js
function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    // <= 保证稳定性：相等时先取左边
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  // 把剩下的接上
  while (i < left.length) result.push(left[i++]);
  while (j < right.length) result.push(right[j++]);
  return result;
}
  • 最好/平均/最坏都是 O(n log n)——性能非常稳定，没有退化风险。
  • 空间 O(n)（合并需要额外数组），稳定。
  • 缺点也在这 O(n)：大数据量下内存开销明显。链表的归并可以做到空间 O(log n)，是链表排序的首选。

2. 快速排序（Quick Sort）

思路：选一个基准（pivot），把数组分区成"小于基准"和"大于基准"两堆，再对两堆递归。 分区操作用原地交换完成。

js
function quickSort(arr, left = 0, right = arr.length - 1) {
  const a = arr; // 原地排序，直接改传入数组（演示用）
  if (left >= right) return a;

  const pivotIndex = partition(a, left, right);
  quickSort(a, left, pivotIndex - 1);
  quickSort(a, pivotIndex + 1, right);
  return a;
}

function partition(a, left, right) {
  // 随机选基准并换到最右，避免有序数组退化
  const rand = left + Math.floor(Math.random() * (right - left + 1));
  [a[rand], a[right]] = [a[right], a[rand]];
  const pivot = a[right];

  let storeIndex = left;
  for (let i = left; i < right; i++) {
    if (a[i] < pivot) {
      [a[i], a[storeIndex]] = [a[storeIndex], a[i]];
      storeIndex++;
    }
  }
  [a[storeIndex], a[right]] = [a[right], a[storeIndex]];
  return storeIndex;
}
  • 平均 O(n log n)，最坏 O(n²)：当每次选到的基准都是最大或最小值（比如对已经有序的数组固定取首/尾元素），分区会退化成一条链。
  • 空间 O(log n)（递归调用栈），不稳定。
  • 工程优化三件套：
    1. 随机基准或三数取中，规避有序数组退化。
    2. 小区间切换插入排序（比如长度 < 16），减少递归开销。
    3. 三路分区处理大量重复元素，避免重复值导致的低效。
  • 综合来看，快排的常数因子小、原地排序、缓存友好，是实践中最快的通用比较排序，因此被大量标准库采用（并配套上述优化）。

五、堆排序：用堆把空间压到 O(1)

堆排序基于二叉堆：用数组存完全二叉树，下标 i 的左右孩子在 2i+1 和 2i+2。大顶堆保证父节点 ≥ 孩子。

js
function heapSort(arr) {
  const a = arr.slice();
  const n = a.length;

  // 1. 建堆：从最后一个非叶子节点开始下沉
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    siftDown(a, i, n);
  }

  // 2. 依次把堆顶（最大值）换到末尾，再修复堆
  for (let end = n - 1; end > 0; end--) {
    [a[0], a[end]] = [a[end], a[0]];
    siftDown(a, 0, end);
  }
  return a;
}

function siftDown(a, i, size) {
  while (true) {
    let largest = i;
    const l = 2 * i + 1;
    const r = 2 * i + 2;
    if (l < size && a[l] > a[largest]) largest = l;
    if (r < size && a[r] > a[largest]) largest = r;
    if (largest === i) break;
    [a[i], a[largest]] = [a[largest], a[i]];
    i = largest;
  }
}
  • 最好/平均/最坏都是 O(n log n)，没有快排的退化风险。
  • 空间 O(1)，原地排序，不稳定。
  • 常数因子比快排大，缓存不友好，所以实践中略慢；常见于"需要最坏情况保证 + 内存受限"的场景。

六、非比较排序：突破 O(n log n) 下界

基于比较的排序，下界是 O(n log n)（决策树证明）。但如果我们利用数据的值域信息，就能做到线性时间。代价是：只适用于特定数据分布。

1. 计数排序（Counting Sort）

统计每个值出现的次数，再用前缀和确定每个元素的最终位置。要求值域范围 k 不能太大，且是整数。

js
function countingSort(arr) {
  if (arr.length <= 1) return arr.slice();

  const min = Math.min(...arr);
  const max = Math.max(...arr);
  const range = max - min + 1;
  const count = new Array(range).fill(0);

  for (const num of arr) count[num - min]++;

  // 前缀和：count[i] 变成 "值 <= i 的元素个数"
  for (let i = 1; i < range; i++) count[i] += count[i - 1];

  // 从后往前填，保证稳定性
  const output = new Array(arr.length);
  for (let i = arr.length - 1; i >= 0; i--) {
    const idx = arr[i] - min;
    output[--count[idx]] = arr[i];
  }
  return output;
}
  • 时间 O(n + k)，空间 O(n + k)，其中 k 是值域大小。
  • 稳定（从后往前填是关键）。
  • 如果值域很大（比如分数是 0 ~ 10^9），k 爆炸，就不适用了。这也是基数排序要按位拆分的原因。

2. 桶排序（Bucket Sort）

把数据按范围分到若干个桶里，每个桶单独排序，再按顺序拼起来。

js
function bucketSort(arr, bucketSize = 5) {
  if (arr.length <= 1) return arr.slice();

  const min = Math.min(...arr);
  const max = Math.max(...arr);
  const bucketCount = Math.floor((max - min) / bucketSize) + 1;
  const buckets = Array.from({ length: bucketCount }, () => []);

  for (const num of arr) {
    buckets[Math.floor((num - min) / bucketSize)].push(num);
  }

  return buckets.flatMap((bucket) => insertionSort(bucket));
}
  • 平均 O(n + k)，最坏 O(n²)（所有元素挤进同一个桶）。
  • 空间 O(n + k)，是否稳定取决于桶内排序（用插入排序则稳定）。
  • 适合数据均匀分布的场景，比如 [0, 1) 区间的浮点数。

3. 基数排序（Radix Sort）

按"个位 → 十位 → 百位"逐位排序，每一位内部用稳定的计数排序。因为低位排好后，高位排序不会破坏低位已建立的顺序，最终全局有序。

js
function radixSort(arr) {
  if (arr.length <= 1) return arr.slice();

  // 只演示非负整数；支持负数需要先按符号拆分
  let max = Math.max(...arr);
  let a = arr.slice();

  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    a = countingSortByDigit(a, exp);
  }
  return a;
}

function countingSortByDigit(arr, exp) {
  const count = new Array(10).fill(0);
  for (const num of arr) count[Math.floor(num / exp) % 10]++;

  for (let i = 1; i < 10; i++) count[i] += count[i - 1];

  const output = new Array(arr.length);
  for (let i = arr.length - 1; i >= 0; i--) {
    const digit = Math.floor(arr[i] / exp) % 10;
    output[--count[digit]] = arr[i];
  }
  return output;
}
  • 时间 O(d(n + k))，d 是最大位数，k 是每一位的基数（十进制为 10）。
  • 空间 O(n + k)，稳定（依赖每一位的稳定子排序）。
  • 适合整数、固定长度字符串，比如手机号、日期等。

七、总览对比表

算法最好平均最坏空间稳定是否原地
冒泡排序O(n)O(n²)O(n²)O(1)是是
选择排序O(n²)O(n²)O(n²)O(1)否是
插入排序O(n)O(n²)O(n²)O(1)是是
希尔排序O(n log n)~O(n^1.3)O(n²)O(1)否是
归并排序O(n log n)O(n log n)O(n log n)O(n)是否
快速排序O(n log n)O(n log n)O(n²)O(log n)否是
堆排序O(n log n)O(n log n)O(n log n)O(1)否是
计数排序O(n + k)O(n + k)O(n + k)O(n + k)是否
桶排序O(n + k)O(n + k)O(n²)O(n + k)是*否
基数排序O(d(n + k))O(d(n + k))O(d(n + k))O(n + k)是否

桶排序的稳定性取决于桶内所用的排序算法；用插入排序则稳定。

八、JS 的 Array.prototype.sort 用的是什么？

一个高频追问：JS 内置的 sort 是什么算法？

  • V8（Chrome、Node.js）自 v7.0 起改用 TimSort（归并 + 插入的混合算法，稳定），此前对短数组用插入排序、长数组用快排变体。
  • 规范（ES2019 起）强制要求 sort 稳定，所以各大引擎都必须实现稳定排序。
  • 默认按字符串比较，数字排序必须传比较函数，否则 [10, 9, 1].sort() 会得到 [1, 10, 9]。
js
[10, 9, 1].sort();                  // [1, 10, 9]  按字符串比较
[10, 9, 1].sort((a, b) => a - b);   // [1, 9, 10]  正确的数字升序

所以工程中：能用内置 sort 就用内置，它是经过大量优化的 TimSort，稳定且性能好。手写排序的意义在于面试和对特定场景的定制。

九、怎么选：一张决策清单

  • 通用场景：直接用 Array.prototype.sort，别造轮子。
  • 需要自己实现 & 追求平均最快：快排 + 随机基准 + 小区间插入排序 + 三路分区。
  • 要求最坏情况也稳、且需要稳定：归并排序（空间换稳定）。
  • 内存极受限、要求最坏 O(n log n)：堆排序。
  • 数据量小或基本有序：插入排序。
  • 整数且值域不大：计数排序。
  • 均匀分布的浮点数：桶排序。
  • 固定位数整数 / 字符串：基数排序。

十、总结

  1. 比较排序的下界是 O(n log n)，冒泡/选择/插入是 O(n²) 的基础款，其中只有插入排序在"基本有序"时能到 O(n)。
  2. 平均 O(n log n) 的主力是归并、快排、堆排：归并稳定但费空间，快排最快但会退化，堆排原地且无退化但常数大。
  3. 快排的三条优化（随机基准、小区间插入、三路分区）是面试和工程都必须说清的加分项。
  4. 计数、桶、基数排序能突破 O(n log n)，前提是放弃"只靠比较"并利用值域信息，且各有适用边界。
  5. 稳定性只有冒泡、插入、归并、计数、桶、基数具备；选择、希尔、快排、堆排不稳定。
  6. JS 内置 sort 是稳定的 TimSort，生产环境优先用它；手写排序用来证明你理解原理和取舍。
评论
0/100