JavaScript常用排序算法中，快速排序是高效O(n log n)的分治算法，选基准值划分数组并递归排序，原地实现但最坏O(n²)，不稳定，适合无序数据。
JavaScript 中常用的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。其中，快速排序和归并排序是两种高效、实用的 O(n log n) 级别排序算法，适合处理中大型数组。它们在原生 Array.prototype.sort() 的底层实现中也常被参考（V8 引擎目前主要用 Timsort，是归并+插入的混合优化版本）。
快速排序（Quicksort）原理与实现
核心思想是“分治”：选一个基准值（pivot），将数组分为三部分——小于 pivot 的、等于 pivot 的、大于 pivot 的，再递归排序前后两部分。
- 不依赖额外空间（原地排序），但最坏时间复杂度为 O(n²)，平均为 O(n log n)
- 不稳定排序（相等元素的相对位置可能改变）
- 适合内存受限、数据基本无序的场景
简易实现（非原地，更易理解）：
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[Math.floor(arr.length / 2)];
const left = [];
const right = [];
const equal = [];
for (let val of arr) {
if (val < pivot) left.push(val);
else if (val > pivot) right.push(val);
else equal.push(val);
}
return [...quickSort(left), ...equal, ...quickSort(right)];
}
// 使用示例
console.log(quickSort([3, 6, 8, 10, 1, 2, 1])); // [1, 1, 2, 3, 6, 8, 10]
归并排序（Merge Sort）原理与实现
也是分治法：把数组不断二分直到单元素，再逐层合并两个已排序子数组，合并时按顺序归并。
立即学习“Java免费学习笔记（深入）”；
- 稳定排序（相等元素顺序不变）
- 时间复杂度稳定为 O(n log n)，但需 O(n) 额外空间
- 适合链表排序或需要稳定性的场景（如按多个字段排序）
递归 + 合并实现：
function mergeSort(arr) {
if (arr.length <= 1) return 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) {
let 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));
}
// 使用示例
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10])); // [3, 9, 10, 27, 38, 43, 82]
实际开发中怎么选？
绝大多数情况直接用原生 sort() 即可，它针对不同长度和数据特征做了高度优化；手动实现主要用于学习、面试或特殊需求（如自定义比较逻辑、避免副作用、排序对象属性等）。
- 对数字排序，记得传比较函数：
[3, 1, 2].sort((a, b) => a - b)，否则会按字符串排序 - 想稳定排序且控制细节，归并排序更可靠；想节省内存且接受不稳定，可考虑快排变体
- 小数组（
基本上就这些。理解思路比死记代码更重要——分治、递归、合并/分区，掌握这两类模式，其他排序也能举一反三。
