不该手写 sort() 替代品，因原生 sort() 已用 Timsort 等优化算法，平均 O(n log n)，且针对真实数据优化；手写易出错，仅在需自定义比较、无内置 sort 或教学时才考虑。
为什么你不该在生产环境手写 sort() 的替代品
JavaScript 的原生 Array.prototype.sort() 在现代引擎（V8、SpiderMonkey、JavaScriptCore）中已普遍采用混合排序（Timsort 或类似优化的 Quicksort + Insertion sort），平均时间复杂度稳定在 O(n log n)，且针对真实数据（部分有序、重复值多等）做了大量启发式优化。手写快排或归并排序不仅难以超越，还容易引入稳定性、边界越界或比较函数副作用等问题。
除非你明确需要：
- 完全控制比较逻辑（如多字段、自定义类型、不可变排序）
- 在无内置
sort()的极简运行时（如某些嵌入式 JS 引擎） - 教学/面试场景下验证理解
否则直接用 arr.sort((a, b) => a - b)（数字）或 arr.sort((a, b) => a.localeCompare(b))（字符串）更安全高效。
quicksort 实现要点与三个典型陷阱
手写快排最常出错的地方不在分区逻辑，而在：递归边界、基准选择、以及原地排序时的索引管理。
立即学习“Java免费学习笔记（深入）”；
一个健壮的递归版本示例（升序）：
function quicksort(arr, low = 0, high = arr.length - 1) {
if (low < high) {
const pivotIndex = partition(arr, low, high);
quicksort(arr, low, pivotIndex - 1);
quicksort(arr, pivotIndex + 1, high);
}
return arr;
}
function partition(arr, low, high) {
const pivot = arr[high]; // 简单取末尾 —— 易退化为 O(n²)，见下文
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}
关键注意点：
-
递归终止条件必须是
low，不是low ，否则会无限递归空子数组 -
pivot若总取arr[high]，遇到已排序数组会触发最坏情况O(n²)；生产级实现应随机选 pivot 或用三数取中 - 原地交换时，
i初始化为low - 1，最后交换位置是i + 1，漏掉这个+1会导致 pivot 错位
mergesort 为什么适合链表但不适合小数组
归并排序稳定、时间复杂度严格 O(n log n)，且天然适合链表（无需额外空间做随机访问），但在 JavaScript 数组上存在明显短板：
- 每次合并需分配新数组，空间复杂度
O(n)，GC 压力大 - 对长度
的子数组，插入排序实际更快（CPU 缓存友好、分支预测成功率高） - V8 的
sort()就在子数组长度 ≤ 10 时自动切到插入排序
因此，纯函数式归并（返回新数组）仅建议用于不可变场景；若真要优化，应实现「底向上归并」+「小数组切换插入排序」：
function mergesort(arr) {
if (arr.length <= 1) return arr;
if (arr.length <= 10) return insertionSort(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, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
时间复杂度不是唯一指标：看真实场景下的表现差异
理论复杂度掩盖了大量工程细节。例如：
-
quicksort平均O(n log n)，但常数因子小，缓存局部性好，在多数随机数组上比mergesort快 20%–30% -
heapsort原地、最坏O(n log n)，但实际慢于快排（比较次数多、缓存不友好），且不稳定，JS 中几乎无人用 -
Timsort（Python/Chrome 使用）在部分有序数组上接近O(n)，这是纯算法描述无法体现的优势
真正影响性能的往往是：数据初始顺序、重复值比例、元素大小（对象 vs 数字）、是否需稳定排序。不要只盯着 Big-O —— 先用 console.time() 测你的真实数据集。
最易被忽略的一点：所有手写排序都默认假设比较函数无副作用。一旦你在 (a, b) => { console.log(a); return a - b } 里加日志，就可能因引擎多次调用比较函数而破坏预期行为 —— 原生 sort() 同样如此，但你更容易忽视这点。
