javascript如何实现排序算法_如何比较不同算法效率

JavaScript排序算法实现需兼顾原理理解与实测性能；冒泡适合教学，快排平均O(n log n)但最坏O(n²)，归并稳定且O(n log n)，内置sort()通常最快；自写适用于学习、面试、特殊环境或定制需求。

JavaScript 中实现排序算法，关键在于理解每种算法的逻辑、时间复杂度和实际运行表现；比较效率不能只看理论，还要结合数据规模、初始顺序、内存占用和 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，要结合真实运行环境测量：

用 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) 额外空间，而快排原地排序（但递归调用栈仍占空间）。

浏览器和 Node.js 的 V8 引擎对 Array.prototype.sort() 有高度优化：

2025-12-30

了解您产品搜索量及市场趋势，制定营销计划