当前位置：首页 > JavaScript

用JS实现快速排序算法

2026-04-04 22:31:37JavaScript

快速排序算法简介

快速排序是一种高效的排序算法，采用分治法策略。通过选择一个基准元素，将数组分为两部分，一部分小于基准，另一部分大于基准，然后递归地对这两部分进行排序。

实现步骤

基准选择与分区 通常选择数组中间元素作为基准，使用双指针法（左指针找大于基准的元素，右指针找小于基准的元素）进行交换，直到左右指针相遇。

递归排序 对分区后的左右子数组递归调用快速排序，直到子数组长度为1或0时停止。

用JS实现快速排序算法

JavaScript代码实现

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[Math.floor(arr.length / 2)];
  const left = [];
  const right = [];
  const equal = [];

  for (const element of arr) {
    if (element < pivot) left.push(element);
    else if (element > pivot) right.push(element);
    else equal.push(element);
  }

  return [...quickSort(left), ...equal, ...quickSort(right)];
}

// 示例用法
const unsortedArray = [3, 6, 8, 10, 1, 2, 1];
const sortedArray = quickSort(unsortedArray);
console.log(sortedArray); // 输出: [1, 1, 2, 3, 6, 8, 10]

代码说明

基准选择：使用数组中间元素作为基准（pivot），避免最坏情况。
分区过程：遍历数组，将元素按大小分配到left、right或equal数组。
递归合并：对left和right递归排序后，与equal数组合并。

时间复杂度

最优/平均情况：O(n log n)
最坏情况（如已排序数组且基准选择不当）：O(n²)

优化建议

随机化基准：选择随机元素作为基准，降低最坏情况概率。
原地排序：通过交换元素减少内存使用（如下方优化代码）。

优化版（原地排序）

function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return;

  const pivotIndex = partition(arr, left, right);
  quickSortInPlace(arr, left, pivotIndex - 1);
  quickSortInPlace(arr, pivotIndex + 1, right);
  return arr;
}

function partition(arr, left, right) {
  const pivot = arr[Math.floor((left + right) / 2)];
  while (left <= right) {
    while (arr[left] < pivot) left++;
    while (arr[right] > pivot) right--;
    if (left <= right) {
      [arr[left], arr[right]] = [arr[right], arr[left]];
      left++;
      right--;
    }
  }
  return left;
}