JS排序算法实现_快速排序优化方案-js教程-PHP中文网

JS排序算法实现_快速排序优化方案

紅蓮之龍

发布： 2025-11-14 22:29:02

原创

307人浏览过

快速排序平均时间复杂度为O(n log n)，通过三数取中和小数组插入排序可优化性能。

js排序算法实现_快速排序优化方案

快速排序是一种高效的排序算法，平均时间复杂度为 O(n log n)，但在极端情况下可能退化到 O(n²)。为了提升其稳定性和性能，可以通过多种方式对基础快排进行优化。以下是 JavaScript 中实现快速排序及其常见优化策略。

1. 基础快速排序实现

快速排序基于分治思想：选择一个基准元素（pivot），将数组分为两部分，左边小于等于 pivot，右边大于 pivot，然后递归处理左右子数组。

function quickSort(arr) {
  if (arr.length <= 1) return arr;
<p>const pivot = arr[Math.floor(arr.length / 2)];
const left = [];
const middle = [];
const right = [];</p><p>for (let val of arr) {
if (val < pivot) left.push(val);
else if (val > pivot) right.push(val);
else middle.push(val);
}</p><p>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;
}
<p>function partition(arr, low, high) {
const pivot = arr[high]; // 选最后一个为基准
let i = low - 1;</p><p>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。

简篇AI排版

AI排版工具，上传图文素材，秒出专业效果！

554

查看详情

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;
    }
<pre class="brush:php;toolbar:false;"><pre class="brush:php;toolbar:false;">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; }