如何正确实现快速排序中的分区逻辑（JavaScript）-js教程-PHP中文网

如何正确实现快速排序中的分区逻辑（JavaScript）

快速排序中若使用两个独立 if 判断而非 if-else 结构，会导致等于基准值（pivot）的元素被遗漏，从而丢失重复元素；同时不合理分区还会降低递归效率，甚至使时间复杂度退化。

快速排序中若使用两个独立 if 判断而非 if-else 结构，会导致等于基准值（pivot）的元素被遗漏，从而丢失重复元素；同时不合理分区还会降低递归效率，甚至使时间复杂度退化。

在你提供的原始代码中，关键问题出在分区（partitioning）逻辑的设计上：

if (array[i]  pivot) {
  greater.push(array[i]);
}
// ❌ 缺失对 array[i] === pivot 的处理！

这段代码仅将元素分为「小于 pivot」和「大于 pivot」两组，而所有等于 pivot 的元素（包括其他与 pivot 值相同的副本）均被跳过——既没进入 less，也没进入 greater，更没有显式保留。由于循环中 i === pivotIndex 时还执行了 continue，唯一保留下来的 pivot 只有最初选中的那一个。结果就是：数组中所有重复值（除首个 pivot 外）全部丢失。

✅ 正确做法是确保每个非 pivot 元素必属其一。常见且健壮的写法是：

if (array[i]  pivot 的情况
}

但注意：此写法虽能保全重复值，却将等于 pivot 的元素全部归入 greater，可能导致分区不均衡（如大量重复值时，less 始终为空），影响性能。更推荐的工业级处理是三路分区（Dutch National Flag）：

Java Maven Code Review

审查Java Maven项目（ZIP压缩包或GitLab仓库URL），检查代码规范、命名、模块边界、可维护性问题以及重复代码。

下载

function quickSort(array) {
  if (array.length <p>这样既保证<strong>稳定性（重复值不丢失）</strong>，又提升分区平衡性，平均时间复杂度稳定在 <em>O(n log n)</em>。</p><p>⚠️ 补充说明：</p>

原始双 if 写法实际等价于 if (x p) {...}，中间的 x === p 是逻辑空洞；
加 continue 无法修复该问题，因为 continue 只跳过当前迭代，不改变条件判断本身的覆盖范围；
性能劣于选择排序/冒泡排序？极可能是因重复值集中导致分区极度倾斜（如 less 恒为空），使递归深度接近 O(n)，总时间退化为 O(n²) —— 这正是快排最坏情况。

✅ 最佳实践建议：