快速排序通过三数取中选基准、三路划分处理重复元素和小数组切换插入排序等优化，显著提升性能。三数取中避免最坏情况，三路划分减少重复元素递归，小数组使用插入排序降低开销，综合使快排在各类数据下均高效稳定。
快速排序是一种高效的排序算法，平均时间复杂度为 O(n log n)，在实际应用中表现优秀。虽然基础版本的快排已经很快，但在处理重复元素多或已接近有序的数据时性能可能下降。通过一些优化手段，可以显著提升其稳定性和效率。
三数取中法选择基准值（Pivot）
传统快排常选取第一个或最后一个元素作为基准，这在数组已有序时会导致最坏情况 O(n²)。为了避免这种情况，采用三数取中法：取首、中、尾三个位置的元素，选择其中的中位数作为 pivot。
这样做能更大概率将数组划分为两个相对均衡的部分，减少递归深度。
示例代码片段：
function medianOfThree(arr, left, right) {
const mid = Math.floor((left + right) / 2);
if (arr[left] > arr[mid]) [arr[left], arr[mid]] = [arr[mid], arr[left]];
if (arr[left] > arr[right]) [arr[left], arr[right]] = [arr[right], arr[left]];
if (arr[mid] > arr[right]) [arr[mid],
arr[right]] = [arr[right], arr[mid]];
return mid;
}
arr[right]] = [arr[right], arr[mid]];
return mid;
}
三路快排处理重复元素
当数组中存在大量重复元素时，传统的二路划分（小于 pivot 和大于 pivot）仍会继续递归处理等于 pivot 的部分，效率低下。使用三路快排可将数组分为三部分：
- 小于 pivot
- 等于 pivot
- 大于 pivot
等于 pivot 的部分无需再排序，直接跳过，大幅减少不必要的递归调用。
实现方式是使用三个指针：lt（小于区右边界）、i（当前扫描位置）、gt（大于区左边界）。
function quickSort3Way(arr, left = 0, right = arr.length - 1) {
if (left >= right) return;
const pivot = arr[left];
let lt = left; // arr[left+1...lt] < pivot
let i = left + 1; // arr[lt+1...i-1] == pivot
let gt = right + 1; // arr[gt...right] > pivot
while (i < gt) {
if (arr[i] < pivot) {
[arr[++lt], arr[i++]] = [arr[i], arr[lt]];
} else if (arr[i] > pivot) {
[arr[--gt], arr[i]] = [arr[i], arr[gt]];
} else {
i++;
}
}
[arr[left], arr[lt]] = [arr[lt], arr[left]];
quickSort3Way(arr, left, lt - 1);
quickSort3Way(arr, gt, right);
}
小数组切换为插入排序
对于元素数量较少的子数组（如长度小于 10），递归开销和分区成本相对较高。此时改用插入排序更为高效，因为它的常数因子小，且对小规模或近似有序数据有良好表现。
可以在递归入口添加判断：
if (right - left <= 10) {
insertionSort(arr, left, right);
return;
}
基本上就这些。结合三数取中、三路划分和小数组优化后，快速排序在各种数据分布下都能保持高性能，适合用于实际开发中的排序需求。不复杂但容易忽略细节。
