JavaScript排序算法实现需兼顾原理理解与实测性能；冒泡适合教学，快排平均O(n log n)但最坏O(n²)，归并稳定且O(n log n)，内置sort()通常最快；自写适用于学习、面试、特殊环境或定制需求。
JavaScript 中实现排序算法，关键在于理解每种算法的逻辑、时间复杂度和实际运行表现；比较效率不能只看理论，还要结合数据规模、初始顺序、内存占用和 JS 引擎特性来实测。
常见排序算法的 JS 实现（带注释）
以下是最常用几种算法的手写实现，便于理解原理和调试：
-
冒泡排序：每次比较相邻元素，把最大值“冒泡”到末尾。适合小数组或教学演示。
function bubbleSort(arr) {
const res = [...arr];
for (let i = 0; i for (let j = 0; j if (res[j] > res[j + 1]) [res[j], res[j + 1]] = [res[j + 1], res[j]]; // 解构交换
}
}
return res;
} -
快速排序：分治法，选基准、分区、递归。平均性能好，但最坏 O(n²)，JS 中注意避免栈溢出（可用迭代优化）。
function quickSort(arr) {
if (arr.length const pivot = arr[Math.floor(arr.length / 2)];
const left = arr.filter(x => x const middle = arr.filter(x => x === pivot);
const right = arr.filter(x => x > pivot);
return [...quickSort(left), ...middle, ...quickSort(right)];
} -
归并排序：稳定、O(n log n) 稳定时间复杂度，适合大数据量或需要稳定性的场景。
function mergeSort(arr) {
if (arr.length 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) {
let result = [], i = 0, j = 0;
while (i if (left[i] else result.push(right[j++]);
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
如何科学比较不同排序算法的效率
不能只看 Big O，要结合真实运行环境测量：
dmap-jsapi-skill
下载
DMap GL地图JSAPI（dmapgl）开发指南。用于编写、审查、调试 DMap 地图 API 代码，涵盖地图初始化、覆盖物渲染、图层管理、事件处理、控件交互等任务。当用户提及 dmap、dmapgl、jsapi‑gl 或相关地图开发需求时自动触发。
-
用 performance.now() 做高精度计时：比 Date.now() 更准，单位为毫秒，支持小数。
const arr = Array.from({length: 10000}, () => Math.random() * 100000);
const start = performance.now();
bubbleSort(arr);
console.log(`冒泡耗时：${performance.now() - start}ms`); - 多轮测试取平均值：单次结果受 GC、CPU 调度干扰大，建议运行 5–10 次取中位数或平均值。
- 测试不同数据特征：分别用随机数组、已排序数组、逆序数组、含大量重复值的数组测试——比如快排在已排序数组上可能退化，而插入排序反而很快。
- 观察内存分配（可选）：用 Chrome DevTools 的 Memory 面板或 performance.memory 查看堆增长，归并排序需 O(n) 额外空间，而快排原地排序（但递归调用栈仍占空间）。
JS 环境下的特殊注意事项
浏览器和 Node.js 的 V8 引擎对 Array.prototype.sort() 有高度优化：
立即学习“Java免费学习笔记（深入）”；
- V8 在数组长度
- 直接调用
arr.sort((a,b) => a - b)通常比手写快排更快，因为底层是 C++ 实现，还做了内联、缓存友好等优化。 - 若需自定义比较逻辑（如按对象属性排序），确保 compareFn 无副作用、返回值严格符合规范（负数/零/正数），否则排序结果不可预测。
什么时候该自己写排序，而不是用 sort()？
- 学习算法原理、准备面试或教学演示
- 嵌入式 JS 环境（如某些 IoT 运行时）不支持完整 ES 标准
- 需要特定行为：比如强制不稳定排序、流式处理超大数组（避免一次性加载）、或与 WebAssembly 协同优化
- 做算法对比实验、性能调优或引擎研究
