快速排序

#快速排序

• 分而治之
• 快速排序原理
• Python 实现
• 平均情况与最糟情况
• 特点

#分而治之

快速排序使用分而治之（D&C，divide and conquer）策略。D&C 解决问题的步骤：

1. 找出基线条件（尽可能简单）
2. 不断将问题分解，直到符合基线条件

土地分方块示例：将 1680m × 640m 的土地均匀分成最大方块。

1680 × 640 → 划出 640×640，余 640×400
 640 × 400 → 划出 400×400，余 400×240
 400 × 240 → 划出 240×240，余 240×160
 240 × 160 → 划出 160×160，余 160×80
 160 × 80  → 80 是 160 的整数倍 → 最大方块 80×80

这就是欧几里得算法（辗转相除法）。D&C 不是算法，而是解决问题的思路。

#快速排序原理

基线条件：数组为空或只有一个元素，已经有序。

递归条件：

1. 选择一个基准值（pivot）
2. 把其余元素分为「比基准值小的」和「比基准值大的」两组
3. 对两组分别递归调用快速排序

[3, 5, 8, 1, 2, 9, 4, 7, 6]
选择 4 作为基准值:

  比基准值小: [3, 1, 2]
  基准值:     [4]
  比基准值大: [5, 8, 9, 7, 6]

结果 = quicksort([3,1,2]) + [4] + quicksort([5,8,9,7,6])

对 [3,1,2] 继续排序（选 1 作基准值）:
  [] + [1] + quicksort([3,2]) → [] + [1] + [2,3] = [1,2,3]

对 [5,8,9,7,6] 继续排序（选 6 作基准值）:
  [5] + [6] + quicksort([8,9,7]) → [5,6,7,8,9]

最终: [1,2,3] + [4] + [5,6,7,8,9] = [1,2,3,4,5,6,7,8,9]

#Python 实现

def quicksort(array):
    if len(array) < 2:
        return array                    # 基线条件：空或单元素
    else:
        pivot = array[0]                # 选第一个元素作基准值
        less = [i for i in array[1:] if i <= pivot]
        greater = [i for i in array[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(greater)

print(quicksort([10, 5, 2, 3]))  # => [2, 3, 5, 10]

实际使用时建议随机选择基准值，而不是总选第一个元素，以避免最糟情况。

#平均情况与最糟情况

最糟情况：如果数组已有序，且总是选第一个元素作基准值，每次只能减少一个元素，调用栈高度为 n：

最糟情况（每次只分出一个元素）:
  [1,2,3,4,5] → pivot=1, less=[], greater=[2,3,4,5]
  [2,3,4,5]   → pivot=2, less=[], greater=[3,4,5]
  [3,4,5]     → pivot=3, less=[], greater=[4,5]
  ...（n 层，每层 O(n) → O(n²)）

最佳情况：基准值将数组平分，调用栈高度为 log n，每层 O(n)：

最佳情况（每次平分）:
  [3,1,2,5,4] → pivot=3, less=[1,2], greater=[5,4]
  [1,2]       → pivot=1, less=[], greater=[2]
  [5,4]       → pivot=5, less=[4], greater=[]
  ...（log n 层，每层 O(n) → O(n log n)）

#大O表示法中的常量

归并排序和快速排序的大O运行时间都是 O(n log n)，但快速排序的平均实际速度更快——因为大O表示法省略了常量，而快速排序的常量比归并排序小。

#特点

• 平均时间复杂度 O(n log n)，实际运行中最快的通用排序算法之一
• 原地排序（标准实现不需要额外数组）
• 不稳定排序
• 性能依赖基准值的选择，随机选择可避免最糟情况
• 递归实现，是分治法的经典应用

#小结

• 快速排序：选基准值 → 分小和大两组 → 递归排序
• 平均 O(n log n)，最糟 O(n²)（可随机选基准值避免）
• 实际应用中最快的排序之一，多数语言内置排序的底层就是快速排序
• 分而治之是一种重要的通用解题思路