如何用JavaScript编写高效的排序算法_常见算法实现与时间复杂度比较【教程】_技术教程

不该手写 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` 实现要点与三个典型陷阱

手写快排最常出错的地方不在分区逻辑，而在：递归边界、基准选择、以及原地排序时的索引管理。

一个健壮的递归版本示例（升序）：

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));
}