当前位置：首页 > JavaScript

递归实现快速排序js

2026-03-01 16:08:46JavaScript

递归实现快速排序js

递归实现快速排序的JavaScript代码

快速排序是一种高效的排序算法，采用分治策略。以下是递归实现的JavaScript代码：

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

  const pivot = arr[0];
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

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

代码说明

基线条件：当数组长度小于等于1时直接返回，无需排序
选择基准值（pivot）：通常选择第一个元素作为基准
分区操作：将小于基准的元素放入left数组，大于等于基准的元素放入right数组
递归调用：对left和right数组分别递归调用quickSort，并将结果与基准值合并

优化版本（原地排序）

上述实现需要额外空间。以下是原地排序的优化版本：

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

  const pivotIndex = partition(arr, left, right);
  quickSort(arr, left, pivotIndex - 1);
  quickSort(arr, pivotIndex + 1, right);

  return arr;
}

function partition(arr, left, right) {
  const pivot = arr[right];
  let i = left;

  for (let j = left; j < right; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }

  [arr[i], arr[right]] = [arr[right], arr[i]];
  return i;
}

时间复杂度分析

最佳情况：O(n log n) - 每次分区都能将数组均匀分成两部分
最差情况：O(n²) - 当数组已经有序或逆序时
平均情况：O(n log n)

使用示例

const unsortedArray = [3, 7, 2, 9, 1, 6, 8, 5, 4];
const sortedArray = quickSort(unsortedArray);
console.log(sortedArray); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

递归实现快速排序js