四、快速排序算法讲解

本文是《排序算法系列》第四篇。前三篇我们走过了 O(n²) 家族（冒泡、插入、选择）、分治代表（归并）、以及两个"进化型"算法（希尔、堆）。这一篇我们聚焦快速排序——实际应用最广泛、平均性能最好的排序算法，也是各大语言标准库sort()的核心实现。如果说归并排序是"稳扎稳打"，那快速排序就是"快刀斩乱麻"。

快速排序（Quick Sort）

1. 核心思想（生活直觉）

想象你在整理一堆杂乱的书，要求按高度从小到大排列。你不会一本本比较，而是：

1. 随便抽一本书作为"基准"（pivot），比如高度 20cm。

2. 把比它矮的放左边，比它高的放右边。

3. 此时，基准书的位置已经确定了——它左边都比它矮，右边都比它高。

4. 对左边那堆和右边那堆，重复同样的操作。

这就是快速排序的核心：分治 + 分区（partition）。每次选一个基准，把数组分成"小于基准"和"大于基准"两部分，基准归位，然后递归处理两边。

和归并排序的区别：归并是"先分到底，再合并"，快排是"边分边治，分完就位"。

2. 详细执行步骤（手把手模拟）

假设我们要对数组升序排列：[5, 1, 4, 2, 8, 3, 7]

我们采用Lomuto 分区方案（最简单易懂），选最后一个元素作为基准。

第 1 轮：选基准 7，分区

数组: [5, 1, 4, 2, 8, 3, 7]
↑ pivot = 7

用指针i标记"小于基准区"的边界，初始i = -1。用j从左到右遍历：

• j=0，arr[0]=5 < 7→i=0，交换arr[0]和arr[0]（自己），数组不变

• j=1，arr[1]=1 < 7→i=1，交换arr[1]和arr[1]，数组不变

• j=2，arr[2]=4 < 7→i=2，交换arr[2]和arr[2]，数组不变

• j=3，arr[3]=2 < 7→i=3，交换arr[3]和arr[3]，数组不变

• j=4，arr[4]=8 > 7→ 不动

• j=5，arr[5]=3 < 7→i=4，交换arr[4]和arr[5]→[5, 1, 4, 2, 3, 8, 7]

遍历结束，把基准放到i+1=5位置：交换arr[5]和arr[6]→[5, 1, 4, 2, 3, 7, 8]

基准 7 归位（下标 5），左边[5, 1, 4, 2, 3]都小于 7，右边[8]大于 7。

第 2 轮：递归处理左边[5, 1, 4, 2, 3]

选基准 3，分区：

• 5 > 3，不动

• 1 < 3，i=0，交换 →[1, 5, 4, 2, 3]

• 4 > 3，不动

• 2 < 3，i=1，交换arr[1]和arr[3]→[1, 2, 4, 5, 3]

基准归位：交换arr[2]和arr[4]→[1, 2, 3, 5, 4]

基准 3 归位，左边[1, 2]，右边[5, 4]。

第 3 轮：递归处理[1, 2]

选基准 2，分区：

• 1 < 2，i=0，不动

基准归位：交换arr[1]和arr[1]，不变 →[1, 2]

第 4 轮：递归处理[5, 4]

选基准 4，分区：

• 5 > 4，不动

基准归位：交换arr[0]和arr[1]→[4, 5]

最终结果：[1, 2, 3, 4, 5, 7, 8]

排序完成！

3. 标准代码实现

Python（Lomuto 分区）：

def quick_sort(arr, low=0, high=None): if high is None: high = len(arr) - 1 if low < high: # 分区，返回基准的最终位置 pi = partition(arr, low, high) # 递归处理左右两边 quick_sort(arr, low, pi - 1) quick_sort(arr, pi + 1, high) return arr 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

Python（Hoare 分区，更高效）：

def quick_sort_hoare(arr, low=0, high=None): if high is None: high = len(arr) - 1 if low < high: pi = partition_hoare(arr, low, high) quick_sort_hoare(arr, low, pi) quick_sort_hoare(arr, pi + 1, high) return arr def partition_hoare(arr, low, high): pivot = arr[(low + high) // 2] # 选中间元素为基准 i, j = low - 1, high + 1 while True: i += 1 while arr[i] < pivot: i += 1 j -= 1 while arr[j] > pivot: j -= 1 if i >= j: return j arr[i], arr[j] = arr[j], arr[i]

Java：

public static void quickSort(int[] arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } private static int partition(int[] arr, int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] <= pivot) { i++; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp; return i + 1; }

C++：

int partition(vector<int>& arr, int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] <= pivot) { i++; swap(arr[i], arr[j]); } } swap(arr[i + 1], arr[high]); return i + 1; } void quickSort(vector<int>& arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } }

代码解读：注意 Lomuto 分区中，i始终指向"小于基准区"的最后一个元素，j负责扫描。遇到小于基准的元素就扩展"小于区"。最后把基准放到i+1位置，此时基准左边全小、右边全大。

4. 时间复杂度与空间复杂度（硬核分析）

最坏情况举例：数组已有序[1, 2, 3, 4, 5]，每次选最后一个元素为基准。

• 第 1 轮：基准 5，分区后[1,2,3,4]和[]，递归深度 1

• 第 2 轮：基准 4，分区后[1,2,3]和[]，递归深度 2

• ...

• 递归深度达到 n，每层扫描 O(n)，总代价O(n²)

递归树对比：

最好情况（均匀分区）： 最坏情况（极度不平衡）：
n n
/ \ /
n/2 n/2 n-1
/ \ / \ /
n/4 ... n-2
深度 log n 深度 n
总代价 O(n log n) 总代价 O(n²)

空间复杂度：递归栈深度。最好 O(log n)，最坏 O(n)。可通过"尾递归优化"把最坏空间降到 O(log n)。

5. 三大关键优化

优化一：随机化基准（避免最坏情况）

不选第一个或最后一个元素，而是随机选一个作为基准，与末尾交换后再分区。这样即使输入有序，也不会退化到 O(n²)。

import random def partition_random(arr, low, high): # 随机选基准，与末尾交换 rand_idx = random.randint(low, high) arr[rand_idx], arr[high] = arr[high], arr[rand_idx] return partition(arr, low, high)

效果：最坏情况的概率降到极低，期望时间复杂度稳定在 O(n log n)。

优化二：三数取中（Median-of-Three）

选arr[low]、arr[mid]、arr[high]三个数的中位数作为基准。这样既避免了有序数据的退化，又比随机化更稳定。

def median_of_three(arr, low, high): mid = (low + high) // 2 # 对三个数排序，把中位数放到 high 位置 if arr[low] > arr[mid]: arr[low], arr[mid] = arr[mid], arr[low] if arr[low] > arr[high]: arr[low], arr[high] = arr[high], arr[low] if arr[mid] > arr[high]: arr[mid], arr[high] = arr[high], arr[mid] # 此时 arr[mid] 是中位数，与 high-1 交换（high 已经是最大） arr[mid], arr[high - 1] = arr[high - 1], arr[mid] return arr[high - 1]

优化三：小数组切换插入排序 + 尾递归优化

当子数组长度小于阈值（通常 7~16）时，直接使用插入排序，避免递归开销。同时用循环代替尾递归，把空间降到 O(log n)。

def quick_sort_optimized(arr, low=0, high=None, threshold=10): if high is None: high = len(arr) - 1 while low < high: if high - low < threshold: insertion_sort_range(arr, low, high) break # 三数取中选基准 pi = partition_median(arr, low, high) # 尾递归优化：先处理较短的一边 if pi - low < high - pi: quick_sort_optimized(arr, low, pi - 1, threshold) low = pi + 1 else: quick_sort_optimized(arr, pi + 1, high, threshold) high = pi - 1 return arr

优化四：三路快排（处理大量重复元素）

当数组有大量重复元素时，标准快排会把等于基准的元素分到一边，导致不平衡。三路快排把数组分成<pivot、==pivot、>pivot三部分，等于基准的元素直接归位，不再参与递归。

def quick_sort_3way(arr, low, high): if low >= high: return pivot = arr[low] lt, gt = low, high # lt: <pivot 的右边界，gt: >pivot 的左边界 i = low while i <= gt: if arr[i] < pivot: arr[lt], arr[i] = arr[i], arr[lt] lt += 1 i += 1 elif arr[i] > pivot: arr[i], arr[gt] = arr[gt], arr[i] gt -= 1 else: i += 1 quick_sort_3way(arr, low, lt - 1) quick_sort_3way(arr, gt + 1, high)

效果：对于[1,1,1,1,1,2,2,2,3,3]这类数据，标准快排可能退化，三路快排仍保持 O(n)。

6. 快速排序 vs 归并排序 vs 堆排序（终极对比）

关键结论：

• 快速排序平均最快，因为它的分区操作是顺序扫描，对 CPU 缓存友好。

• 快速排序的最坏 O(n²)可通过随机化基准、三数取中、内省排序等优化避免。

• 归并排序的稳定 + 最坏保证适合对稳定性有要求的场景。

• 堆排序的O(1) 空间 + 最坏保证适合内存受限场景。

各大语言的选择：

7. 适用场景

• 通用内存排序：大多数场景下快排是首选，速度最快。

• 大规模随机数据：平均 O(n log n)，实际常数因子最小。

• 对稳定性无要求：如单纯数值排序。

• 缓存敏感场景：快排的顺序访问模式对 CPU 缓存友好。

• 作为内省排序的核心：C++std::sort、Gosort.Slice的基础。

• Top-K 问题：用快排的 partition 思想，只需 O(n) 时间找到第 K 大元素（QuickSelect 算法）。