Part 3.2：快速排序：分治思想的经典应用

引言：最快的排序算法？

在上一篇文章中，我们学习了三种 O(n²) 的基础排序算法。今天，我们将迈入 O(n log n) 的高效排序世界，学习其中最著名、应用最广泛的算法——**快速排序 (Quick Sort)**。

快速排序由图灵奖得主 Tony Hoare 于 1960 年提出，因其出色的平均性能和原地排序的特性，成为了许多编程语言标准库排序函数的首选实现（如 C 的 qsort）。

为什么快速排序如此重要？

面试高频：快速排序是面试中最常考的排序算法，尤其是其分区（Partition）过程和各种优化策略。
实际应用：在大多数情况下，快速排序比其他 O(n log n) 算法（如归并排序、堆排序）更快。
思想价值：快速排序是分治思想的经典体现，理解它有助于你掌握递归和分治策略。

本文将带你深入理解快速排序的原理、实现和优化，让你真正掌握这个”快”字当头的算法。

1. 核心原理：分治三部曲

快速排序采用分治 (Divide and Conquer) 策略，其核心思想可以概括为三个步骤：

**选择基准 (Pivot)**：从数组中选择一个元素作为”基准”。
**分区 (Partition)**：重新排列数组，使得所有小于基准的元素都在基准的左边，所有大于基准的元素都在基准的右边。此时，基准元素就处于其最终排序后的正确位置。
递归排序：对基准左边和右边的两个子数组分别递归地执行快速排序。

关键图示：快速排序的分治过程

图示：

初始数组: [3, 7, 8, 5, 2, 1, 9, 5, 4]

选择基准: 4 (最后一个元素)
分区后:  [3, 2, 1, 4, 7, 8, 9, 5, 5]
                  ↑ 基准在正确位置

递归左边: [3, 2, 1]
递归右边: [7, 8, 9, 5, 5]

2. 核心操作：分区 (Partition)

分区是快速排序的核心，也是面试中最常考的部分。

Lomuto 分区方案（最常用）

思路：

选择最后一个元素作为基准 pivot。
维护一个指针 i，表示”小于基准的区域”的边界。
用指针 j 遍历数组，如果 arr[j] < pivot，就将 arr[j] 与 arr[i] 交换，并将 i 右移。
遍历结束后，将基准与 arr[i] 交换，此时基准就在正确位置。

动画式案例

数组：[3, 7, 8, 5, 2, 1, 9, 5, 4]，基准 pivot = 4

初始：i = -1
j = 0，arr[0] = 3 < 4，i++，交换 arr[0] 和 arr[0] → [3, 7, 8, 5, 2, 1, 9, 5, 4]，i = 0
j = 1，arr[1] = 7 >= 4，不交换
j = 2，arr[2] = 8 >= 4，不交换
j = 3，arr[3] = 5 >= 4，不交换
j = 4，arr[4] = 2 < 4，i++，交换 arr[1] 和 arr[4] → [3, 2, 8, 5, 7, 1, 9, 5, 4]，i = 1
j = 5，arr[5] = 1 < 4，i++，交换 arr[2] 和 arr[5] → [3, 2, 1, 5, 7, 8, 9, 5, 4]，i = 2
遍历结束，交换 arr[i+1] 和 pivot → [3, 2, 1, 4, 7, 8, 9, 5, 5]

结果：基准 4 在索引 3 的正确位置。

伪代码

function partition(arr, low, high):
  pivot = arr[high]
  i = low - 1
  
  for j from low to high-1:
    if arr[j] < pivot:
      i = i + 1
      swap(arr[i], arr[j])
  
  swap(arr[i+1], arr[high])
  return i + 1

function quickSort(arr, low, high):
  if low < high:
    pi = partition(arr, low, high)
    quickSort(arr, low, pi - 1)
    quickSort(arr, pi + 1, high)

Python 实现

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# 使用
arr = [3, 7, 8, 5, 2, 1, 9, 5, 4]
quick_sort(arr, 0, len(arr) - 1)
print(arr) # 输出: [1, 2, 3, 4, 5, 5, 7, 8, 9]

3. 复杂度分析

时间复杂度

最好情况：O(n log n)。每次分区都能将数组平分。
平均情况：O(n log n)。
最坏情况：O(n²)。每次分区都极度不平衡（如已排序数组，且选择第一个或最后一个元素作为基准）。

空间复杂度

O(log n)：递归调用栈的深度（平均情况）。
O(n)：最坏情况下的递归深度。

稳定性

不稳定。分区过程中的交换可能改变相等元素的相对位置。

4. 三大优化策略

4.1 随机化基准 (Randomized Pivot)

问题：固定选择最后一个元素作为基准，在数组已排序或接近排序时，会导致最坏情况 O(n²)。

解决：随机选择一个元素作为基准，然后将其与最后一个元素交换。

import random

def partition_randomized(arr, low, high):
    random_index = random.randint(low, high)
    arr[random_index], arr[high] = arr[high], arr[random_index]
    return partition(arr, low, high)

效果：将最坏情况的概率降到极低，平均性能更稳定。

4.2 三路快排 (3-Way Quick Sort)

问题：当数组中有大量重复元素时，普通快速排序效率低下。

解决：将数组分成三部分：小于基准、等于基准、大于基准。

应用：荷兰国旗问题（Dutch National Flag Problem）。

4.3 尾递归优化

问题：递归深度过大可能导致栈溢出。

解决：将其中一个递归调用改为迭代，优先递归较小的子数组。

5. 快速排序 vs 归并排序

特性	快速排序	归并排序
平均时间	`O(n log n)`	`O(n log n)`
最坏时间	`O(n²)`	`O(n log n)`
空间复杂度	`O(log n)`	`O(n)`
稳定性	不稳定	稳定
原地排序	是	否
实际性能	通常更快	稳定但需额外空间