快速排序

快速排序选择一个基准值，将元素分为小于基准、等于基准和大于基准的部分，再递归处理左右区间。

实现

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

  const pivot = arr[Math.floor(arr.length / 2)]
  const less = []
  const equal = []
  const greater = []

  for (const value of arr) {
    if (value < pivot) less.push(value)
    else if (value > pivot) greater.push(value)
    else equal.push(value)
  }

  return [...quickSort(less), ...equal, ...quickSort(greater)]
}

复杂度

• 平均时间复杂度：O(n log n)
• 最坏时间复杂度：O(n²)，例如每次都选中极端值作为基准
• 空间复杂度：平均 O(log n)；上面的简洁实现会额外创建分区数组
• 稳定性：通常不稳定

工程实现通常会随机选择基准值，或使用三数取中降低退化概率。