快速排序的核心逻辑是分治+原地分区：每次选pivot将数组划分为小于、等于、大于三部分，用双指针原地交换实现O(log n)空间复杂度。
快速排序的核心逻辑是什么
快速排序不是靠“快”命名的，而是靠“分治+原地分区”的策略实现高效排序。它的关键不是递归本身，而是每次选一个 pivot（基准值），把数组划分为三部分：小于 pivot、等于 pivot、大于 pivot。现代 JS 实现通常用“双指针原地分区”，避免额外空间开销。
如何写一个不新建数组的原地快排
新建数组（如 filter 拆分）看似简洁，但时间复杂度没变，空间却升到 O(n)；而原地版本空间复杂度是 O(log n)（仅递归栈）。下面是最简可用的原地实现：
function quickSort(arr, left = 0, right = arr.length - 1) {
if (left >= right) return;
const pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
function partition(arr, left, right) {
const pivot = arr[right]; // 取最右为 pivot
let i = left;
for (let j = left; j < right; j++) {
if (arr[j] <= pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
[arr[i], arr[right]] = [arr[right], arr[i]];
return i;
}
-
partition函数必须返回最终pivot落入的位置，否则递归区间会错乱 - 切勿在
partition中使用arr.sort()或slice().sort()—— 那就不是快排了 - 若输入是只读数组（如
Object.freeze），需先arr.slice()拷贝，否则会报错
为什么你的快排在大量重复元素时变慢
当数组含大量相同值（如 [5,5,5,5,5]），默认取末尾为 pivot 会导致每次只减少一个元素，退化成 O(n²)。解决方法不是换语言，而是改分区策略：
- 用三路快排（Dutch National Flag）：分出 pivot / =
pivot/ >pivot三段，equal区直接跳过递归 - 随机选
pivot：在partition前加[arr[right], arr[Math.floor(Math.random() * (right - left + 1)) + left]] = [arr[Math.floor(...)], arr[right]]; - 对小数组（如
right - left ）切回插入排序，减少递归开销
和 Array.prototype.sort() 的区别在哪
JS 引擎内置的 sort() 不是快排 —— V8 用的是 TimSort（归并+插入混合），SpiderMonkey 用 QuickSort 变种但做了深度优化（如内省式切换、堆栈保护）。你手写的快排在以下场景会明显更慢或出错：
立即学习“Java免费学习笔记（深入）”；
- 未处理
undefined/null/NaN：内置sort()会把undefined排最后，而你的arr[j] 可能产生NaN比较结果 - 未考虑比较函数：内置支持
(a,b) => a - b，而手写版要自己把比较逻辑塞进partition - 未限制递归深度：极端有序数组可能触发栈溢出，V8 有自动降级机制，你得自己加
if (depth > 32) return insertionSort(arr, left, right);
真正需要手写快排，通常是为了教学、面试，或嵌入式环境无法依赖引擎实现——而不是为了比 sort() 更快。
