快速排序平均时间复杂度为O(n log n)，通过三数取中和小数组插入排序可优化性能。
快速排序是一种高效的排序算法，平均时间复杂度为 O(n log n)，但在极端情况下可能退化到 O(n²)。为了提升其稳定性和性能，可以通过多种方式对基础快排进行优化。以下是 JavaScript 中实现快速排序及其常见优化策略。
1. 基础快速排序实现
快速排序基于分治思想：选择一个基准元素（pivot），将数组分为两部分，左边小于等于 pivot，右边大于 pivot，然后递归处理左右子数组。
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[Math.floor(arr.length / 2)];
const left = [];
const middle = [];
const right = [];
for (let val of arr) {
if (val < pivot) left.push(val);
else if (val > pivot) right.push(val);
else middle.push(val);
}
return [...quickS
ort(left), ...middle, ...quickSort(right)];
}
ort(left), ...middle, ...quickSort(right)];
}这个版本清晰易懂，但使用了额外空间，且在重复元素多时效率不高。
2. 原地快排（In-place 快排）
通过双指针在原数组上操作，减少空间占用，提升缓存利用率。
function quickSortInPlace(arr, low = 0, high = arr.length - 1) {
if (low < high) {
const pivotIndex = partition(arr, low, high);
quickSortInPlace(arr, low, pivotIndex - 1);
quickSortInPlace(arr, pivotIndex + 1, high);
}
return arr;
}
function partition(arr, low, high) {
const pivot = arr[high]; // 选最后一个为基准
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}
这种实现空间复杂度降到 O(log n)（递归栈），是更实用的版本。
3. 优化方案一：三数取中法选基准
避免最坏情况（如已排序数组），不直接选首尾或中间元素，而是取头、中、尾三个元素的中位数作为 pivot。
function medianOfThree(arr, low, mid, high) {
if (arr[low] > arr[mid]) [arr[low], arr[mid]] = [arr[mid], arr[low]];
if (arr[mid] > arr[high]) [arr[mid], arr[high]] = [arr[high], arr[mid]];
if (arr[low] > arr[mid]) [arr[low], arr[mid]] = [arr[mid], arr[low]];
return mid;
}在 partition 前调用该函数获取更合理的 pivot 索引，可显著减少比较次数。
4. 优化方案二：小数组改用插入排序
当子数组长度小于某个阈值（如 10）时，插入排序比快排更快，因常数项更小。
function insertionSort(arr, low, high) {
for (let i = low + 1; i <= high; i++) {
const key = arr[i];
let j = i - 1;
while (j >= low && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}修改主函数逻辑：
function optimizedQuickSort(arr, low = 0, high = arr.length - 1) {
while (low < high) {
if (high - low < 10) {
insertionSort(arr, low, high);
break;
}
const pivotIndex = partition(arr, low, high);
// 优化：先处理较小的一边，减少递归栈深度
if (pivotIndex - low < high - pivotIndex) {
optimizedQuickSort(arr, low, pivotIndex - 1);
low = pivotIndex + 1;
} else {
optimizedQuickSort(arr, pivotIndex + 1, high);
high = pivotIndex - 1;
}}
return arr;
}
5. 其他优化建议
- 三路快排（Dutch National Flag）：适用于大量重复元素。将数组分为小于、等于、大于 pivot 三部分，等于的部分不再参与后续排序。
- 随机化 pivot：随机选择基准，降低被构造数据攻击的风险。
- 尾递归优化：手动控制递归方向，优先处理小分区，使栈深度最大为 O(log n)。
基本上就这些。结合三数取中、小数组切换插入排序、三路划分等策略，可以让快排在各种输入下都表现稳健。实际开发中虽然很少手写排序，但理解这些优化有助于深入掌握算法设计思想。
