17370845950

快速排序的核心逻辑是分治+原地分区：每次选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 变种但做了深度优化（如内省式切换、堆栈保护）。你手写的快排在以下场景会明显更慢或出错：

• 未处理 undefined / null / NaN：内置 sort() 会把 undefined 排最后，而你的 arr[j] 可能产生 NaN 比较结果
• 未考虑比较函数：内置支持 (a,b) => a - b，而手写版要自己把比较逻辑塞进 partition
• 未限制递归深度：极端有序数组可能触发栈溢出，V8 有自动降级机制，你得自己加 if (depth > 32) return insertionSort(arr, left, right);

真正需要手写快排，通常是为了教学、面试，或嵌入式环境无法依赖引擎实现——而不是为了比 sort() 更快。