用JS实现快速排序算法

快速排序的原理

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

代码实现

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

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

  for (let 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]

优化版本（原地排序）

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

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²)（当数组已经排序或逆序时）

注意事项

• 对于小型数组（如长度小于10），插入排序可能比快速排序更高效。
• 基准选择策略会影响性能，常见方法包括选择第一个元素、最后一个元素、中间元素或随机元素。
• 快速排序是不稳定的排序算法，相等元素的相对位置可能会改变。