排序算法深度解析

一句话概括

没有一种排序在所有场景都最优——它们各自在时间、空间、稳定性上做了不同取舍。面试常考的不是”会不会写快排”，而是”为什么快排最坏 O(n²)、为什么堆排实际比快排慢、为什么有时候必须稳定”。

日常 99% 场景直接 Array.sort()（V8 用 TimSort）就够；但当你遇到”内存受限”“Top K”“大量重复”时，得知道换哪把刀。

核心知识点

1. 快速排序：平均最快，基准是命门

分治：选基准 → 分区（小的在左、大的在右）→ 递归两边。平均 O(n log n)，最坏 O(n²)（每次分区极不平衡，如已排序数组还选第一个当基准）。

// 原地 Lomuto 分区
function partition(arr, left, right) {
  const pivot = arr[right];
  let i = left;
  for (let j = left; j < right; j++) {
    if (arr[j] <= pivot) { [arr[i], arr[j]] = [arr[j], arr[i]]; i++; }
  }
  [arr[i], arr[right]] = [arr[right], arr[i]]; // 基准归位
  return i;
}
function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return arr;
  const p = partition(arr, left, right);
  quickSort(arr, left, p - 1);
  quickSort(arr, p + 1, right);
  return arr;
}

// ❌ 选第一个/最后一个当基准：对已排序数组退化 O(n²)
// ✅ 随机基准或三数取中，把最坏概率降到极低
function quickSortRandom(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return arr;
  const r = left + Math.floor(Math.random() * (right - left + 1));
  [arr[r], arr[right]] = [arr[right], arr[r]]; // 随机基准
  const p = partition(arr, left, right);
  quickSortRandom(arr, left, p - 1);
  quickSortRandom(arr, p + 1, right);
  return arr;
}

2. 归并排序：最坏也 O(n log n)，稳定但吃空间

分治但”先切后合”：从中间切两半各自排好，再 merge 两个有序数组。无论输入多糟都是 O(n log n)，且稳定；代价是 O(n) 额外空间。

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = arr.length >> 1;
  return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)));
}
function merge(left, right) {
  const res = []; let i = 0, j = 0;
  while (i < left.length && j < right.length)
    res.push(left[i] <= right[j] ? left[i++] : right[j++]); // <= 保证稳定
  return res.concat(left.slice(i), right.slice(j));
}

3. 堆排序：原地 O(1) 空间，最坏 O(n log n)

建大顶堆 → 反复把堆顶（最大）换到末尾、再下沉调整。原地、最坏稳 O(n log n)，但不稳定，且缓存不友好（访问跳跃）导致实际比快排慢 2~5 倍。

function heapSort(arr) {
  const n = arr.length;
  for (let i = (n >> 1) - 1; i >= 0; i--) heapify(arr, n, i); // 建堆 O(n)
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]]; // 堆顶换到末尾
    heapify(arr, i, 0);                  // 下沉 O(log n)
  }
  return arr;
}
function heapify(a, size, i) {
  let largest = i;
  const l = 2 * i + 1, 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) { [a[i], a[largest]] = [a[largest], a[i]]; heapify(a, size, largest); }
}

4. 一张表记住怎么选

算法	平均	最坏	空间	稳定	特点
冒泡	O(n²)	O(n²)	O(1)	✅	教学用，实际别用
快排	O(n log n)	O(n²)	O(log n)	❌	平均最快、缓存友好
归并	O(n log n)	O(n log n)	O(n)	✅	性能稳、省心
堆排	O(n log n)	O(n log n)	O(1)	❌	原地、适合 Top K

其实你每天都在用

• Array.sort()：V8 用 TimSort（归并变体），对基本类型还用双轴快排，几乎覆盖你所有排序需求
• 表格点表头排序：要”先按 A 列、再按 B 列”多级排序 → 必须稳定排序，否则 A 列顺序被搅乱
• 排行榜取前 100 名（Top K）：用大小为 K 的小顶堆遍历一遍 O(n log K)，不必全排
• 找第 K 大元素：QuickSelect（快排变体），平均 O(n)，不排序整个数组
• 大量重复值的大数组：三路快排把”等于基准”单独成段，性能逼近 O(n)
• 近乎有序的数组：优化版冒泡 / 插入可 O(n) 提前结束，TimSort 更是直接利用有序片段

常见误解（FAQ）

❌ 误区一：”快排永远比堆排快，所以一律用快排”

快排平均快，但最坏 O(n²)、不稳定、且需要递归栈。堆排原地 O(1)、最坏稳 O(n log n)，在”内存受限”或”只要 Top K”时更合适。该看数据特征选，不是认死理。

❌ 误区二：”稳定性无所谓，反正排完结果一样”

相等元素相对顺序在”多级排序”里要命。先按时间排、再按类型排——用不稳定排序，同类型内部的”时间先后”会被打乱，Excel / 数据库的”先排 A 再排 B”就是靠稳定排序保序的。

❌ 误区三：”排序下界是 O(n log n)，所以不可能更快”

那是”基于比较”的排序下界。非比较排序（计数、桶、基数）可以做到 O(n + k)，前提是数据有范围约束。面试题说”100 以内整数排序”时，计数排序才是正解。

❌ 误区四：”归并排序空间 O(n)，不如快排原地好”

对，但 O(n) 换来的是”最坏也有保障 + 稳定”，在”数据分布不可预测、又要稳定”时这是最稳的选择。V8 的 TimSort 本质就是归并系，可见工程上它更被信赖。

一句话总结

排序没有”最好”，只有”最合适”——快排赢在平均与缓存、归并赢在稳定与保底、堆排赢在原地与 Top K；记住它们的复杂度与稳定性边界，你就能在”数据特征 + 约束”面前选出对的刀。