排序算法
02-高级算法2026/11/14
排序是所有算法题的底座，真正要掌握的不是六份代码，而是每种排序在时间、空间、稳定性上的取舍。
线上订单列表十万条，前端排一次序卡了 300ms，改后端分页后顺滑。选哪种排序，由数据规模、分布、内存和稳定性共同决定。
复杂度对比
| 算法 | 最好 | 平均 | 最坏 | 空间 | 稳定 | 原地 |
|---|---|---|---|---|---|---|
| 冒泡排序 | 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 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) | 否 | 是 |
| TimSort | O(n) | O(n log n) | O(n log n) | O(n) | 是 | 否 |
稳定性指相等元素相对顺序不变，跨位置交换会破坏它，选择排序和快排因此不稳定。
三种 O(n²)：插入排序活得最久
冒泡每轮把最大值冒到末尾，无交换即提前退出。选择排序每轮选最小值放到已排序区末尾，交换少但要扫完整个数组。插入排序把当前元素插进前面有序区的正确位置。
function bubbleSort(a) {
for (let end = a.length - 1; end > 0; end--) {
let swapped = false;
for (let i = 0; i < end; i++)
if (a[i] > a[i + 1]) { [a[i], a[i + 1]] = [a[i + 1], a[i]]; swapped = true; }
if (!swapped) return a;
}
return a;
}
function selectionSort(a) {
for (let i = 0; i < a.length; i++) {
let min = i;
for (let j = i + 1; j < a.length; j++) if (a[j] < a[min]) min = j;
[a[i], a[min]] = [a[min], a[i]];
}
return a;
}
function insertionSort(a) {
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--];
a[j + 1] = cur;
}
return a;
}
插入排序在基本有序时内层 while 几乎不执行，退化成 O(n)，移动是连续写，缓存友好。V8 的 sort 在短数组上直接用它：常数因子小于归并递归，TimSort 切出的 run 又有序。
归并排序：稳定的代价是 O(n) 空间
分治是"拆到单元素有序，再两两合并"。合并用双指针，相等时取左边，稳定性来自这个 <=。
function mergeSort(a) {
if (a.length <= 1) return a;
const mid = a.length >> 1;
const left = mergeSort(a.slice(0, mid));
const right = mergeSort(a.slice(mid));
const res = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) res.push(left[i] <= right[j] ? left[i++] : right[j++]);
while (i < left.length) res.push(left[i++]);
while (j < right.length) res.push(right[j++]);
return res;
}