快速排序通过三数取中选基准、三路划分处理重复元素、小数组切换插入排序及尾递归优化，可显著提升性能与稳定性。
快速排序是一种高效的排序算法，平均时间复杂度为 O(n log n)，在实际应用中表现优秀。但基础版本在处理重复元素或已排序数组时可能退化到 O(n²)。通过一些优化手段，可以显著提升其稳定性和性能。
三数取中法选择基准（Pivot）
传统快排常选取第一个或最后一个元素作为基准，这在数组已排序时会导致分割极不平衡。使用三数取中法能有效避免这一问题。
从当前子数组的首、中、尾三个位置选出中位数作为基准，放在末尾参与分区，提高分割的均衡性。
做法示例：- 取 left、mid、right 三个索引对应的值
- 比较三者，将中位数交换到 right - 1 位置或直接作为 pivot 值
- 用该值进行 partition 操作
三路快排（Dutch National Flag）
当数组中存在大量重复元素时，传统二路划分效率较低。三路快排将数组分为三部分：小于、等于、大于基准值的区域，避免对相等元素重复排序。
立即学习“Java免费学习笔记（深入）”；
Java Maven Common
下载
Java Maven 项目审查工作流的通用输入处理。当 Java Maven 项目以 ZIP压缩包或 GitLab 仓库 URL 形式提供且需要...时使用。
- 维护三个指针：lt（小于区右边界）、i（当前扫描位置）、gt（大于区左边界）
- 遍历时，若元素小于 pivot，与 lt 交换并扩展小于区；若等于，继续前进；若大于，与 gt 交换并将 gt 左移
- 递归仅对小于区和大于区进行
这种策略在处理如 [2,1,3,1,2,1,2] 这类数据时优势明显。
小数组切换为插入排序
对于元素数量较少的子数组（通常小于 10），递归调用快排开销较大。此时改用插入排序更高效，因为其常数因子小且对近序数组表现好。
实现建议：- 在递归入口判断数组长度
- 若长度 ≤ 10，调用插入排序并返回
- 否则继续执行快排逻辑
尾递归优化
快排递归调用通常先处理一个分区，再处理另一个。可通过循环代替第二次递归调用，减少栈深度。
处理完较小的分区后，用循环更新边界来处理较大的分区，避免深层递归导致栈溢出。
技巧：- 比较左右分区大小
- 递归处理小分区
- 循环处理大分区（修改边界参数）
基本上就这些。结合三数取中、三路划分、小数组切换和尾调用优化，可以让 JavaScript 中的快排更加健壮高效。虽然 V8 引擎的 Array.prototype.sort() 已高度优化（采用 Timsort），但在特定场景手动实现仍有价值。不复杂但容易忽略。
