js快速排序的实现

快速排序的原理

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

实现步骤

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)];
}

优化版本（原地排序）

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    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 log n)
• 最坏情况：O(n²)（当数组已经有序时）

使用示例

const arr = [5, 3, 8, 4, 2];
console.log(quickSort(arr)); // [2, 3, 4, 5, 8]