快速排序平均时间复杂度为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) right.push(val);else middle.push(val);}
return [...quickSort(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 = 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)。
基本上就这些。结合三数取中、小数组切换插入排序、三路划分等策略，可以让快排在各种输入下都表现稳健。实际开发中虽然很少手写排序，但理解这些优化有助于深入掌握算法设计思想。
以上就是JS排序算法实现_快速排序优化方案的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1538876.html
微信扫一扫 
支付宝扫一扫 
