登录
首页 >  文章 >  前端

快速排序优化版实现详解

时间：2026-05-25 17:47:14 141浏览 收藏

本文深入解析了快速排序的三大核心优化策略——三数取中法选取基准以避免最坏情况、三路划分高效处理大量重复元素、以及小数组自动切换至插入排序以降低递归开销，全面提升了算法在各类实际数据（如近序、含大量重复值等）下的性能、稳定性与实用性，让经典快排真正兼具理论优雅与工程高效。

JavaScript排序算法_快速排序优化实现

快速排序是一种高效的排序算法，平均时间复杂度为 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;
}

三路快排处理重复元素

当数组中存在大量重复元素时，传统的二路划分（小于 pivot 和大于 pivot）仍会继续递归处理等于 pivot 的部分，效率低下。使用三路快排可将数组分为三部分：

  • 小于 pivot
  • 等于 pivot
  • 大于 pivot

等于 pivot 的部分无需再排序，直接跳过，大幅减少不必要的递归调用。

实现方式是使用三个指针：lt（小于区右边界）、i（当前扫描位置）、gt（大于区左边界）。

function quickSort3Way(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return;
<p>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</p><p>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]];</p><p>quickSort3Way(arr, left, lt - 1);
quickSort3Way(arr, gt, right);
}</p>

小数组切换为插入排序

对于元素数量较少的子数组（如长度小于 10），递归开销和分区成本相对较高。此时改用插入排序更为高效，因为它的常数因子小，且对小规模或近似有序数据有良好表现。

可以在递归入口添加判断：

if (right - left <= 10) {
  insertionSort(arr, left, right);
  return;
}

基本上就这些。结合三数取中、三路划分和小数组优化后，快速排序在各种数据分布下都能保持高性能，适合用于实际开发中的排序需求。不复杂但容易忽略细节。

今天关于《快速排序优化版实现详解》的内容就介绍到这里了，是不是学起来一目了然！想要了解更多关于的内容请关注golang学习网公众号！

资料下载
相关阅读
更多>
最新阅读
更多>
课程推荐
更多>