快速排序

快速排序通过选择一个基准元素将数组划分为两个子数组，递归地对子数组进行排序，实现高效排序。

核心思想

快速排序采用分治法策略：

1. 选基准：从数组中选择一个元素作为基准（pivot）
2. 划分：将数组中小于基准的元素放在左边，大于基准的放在右边
3. 递归：对左右两个子数组递归执行上述过程

算法实现

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
  return arr;
}
 
function partition(arr, low, high) {
  const pivot = arr[high];
  let i = low - 1;
  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

时间复杂度

• 平均：O(n log n)
• 最差：O(n²) — 当数组已经有序或逆序时
• 最佳：O(n log n) — 每次划分恰好平分数组

空间复杂度

• 递归调用栈：O(log n) 平均，O(n) 最差
• 原地版本：只需要 O(1) 额外空间

优化策略

1. 三数取中法：选择首、中、尾三个元素的中位数作为基准
2. 随机化版本：随机选择基准元素，避免最差情况
3. 尾递归优化：优先处理小区间，减少递归深度
4. 插入排序混合：数组较小时使用插入排序

优势与局限

优势：

• 平均性能优秀，是实际应用中常用的排序算法
• 原地排序，空间效率高
• 缓存友好（对数组操作）

局限：

• 不稳定排序（相等元素可能改变相对顺序）
• 最差性能较差
• 递归深度可能导致栈溢出

关联

• 归并排序 — 另一种分治排序算法，稳定但需要额外空间
• 堆排序 — 基于完全二叉树的排序算法
• 排序算法对比 — 各排序算法的复杂度对比
• 算法复杂度分析 — 时间与空间复杂度分析方法