★ FEATURED ARTICLE 本文是《排序算法系列》第四篇。前三篇我们走过了 O(n²) 家族冒泡、插入、选择、分治代表归并、以及两个进化型算法希尔、堆。这一篇我们聚焦快速排序——实际应用最广泛、平均性能最好的排序算法也是各大语言标准库sort()的核心实现。如果说归并排序是稳扎稳打那快速排序就是快刀斩乱麻。快速排序Quick Sort1. 核心思想生活直觉想象你在整理一堆杂乱的书要求按高度从小到大排列。你不会一本本比较而是随便抽一本书作为基准pivot比如高度 20cm。把比它矮的放左边比它高的放右边。此时基准书的位置已经确定了——它左边都比它矮右边都比它高。对左边那堆和右边那堆重复同样的操作。这就是快速排序的核心分治 分区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从左到右遍历j0arr[0]5 7→i0交换arr[0]和arr[0]自己数组不变j1arr[1]1 7→i1交换arr[1]和arr[1]数组不变j2arr[2]4 7→i2交换arr[2]和arr[2]数组不变j3arr[3]2 7→i3交换arr[3]和arr[3]数组不变j4arr[4]8 7→ 不动j5arr[5]3 7→i4交换arr[4]和arr[5]→[5, 1, 4, 2, 3, 8, 7]遍历结束把基准放到i15位置交换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 3i0交换 →[1, 5, 4, 2, 3]4 3不动2 3i1交换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 2i0不动基准归位交换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. 标准代码实现PythonLomuto 分区def quick_sort(arr, low0, highNone): 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 1PythonHoare 分区更高效def quick_sort_hoare(arr, low0, highNone): 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]Javapublic 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; }Cint partition(vectorint 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(vectorint 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负责扫描。遇到小于基准的元素就扩展小于区。最后把基准放到i1位置此时基准左边全小、右边全大。4. 时间复杂度与空间复杂度硬核分析维度详情最坏时间复杂度O(n²)—— 每次选的基准都是最大或最小值分区极度不平衡最好时间复杂度O(n log n) —— 每次基准都正好是中位数分区均匀平均时间复杂度O(n log n)—— 随机数据下表现优异空间复杂度O(log n) —— 递归栈深度最坏 O(n)稳定性不稳定—— 分区时远距离交换会打乱相等元素顺序最坏情况举例数组已有序[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, low0, highNone, threshold10): 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 堆排序终极对比对比维度快速排序归并排序堆排序平均时间复杂度O(n log n)O(n log n)O(n log n)最坏时间复杂度O(n²)O(n log n)O(n log n)空间复杂度O(log n)O(n)O(1)稳定性不稳定稳定不稳定实际速度最快中等较慢缓存友好度高顺序访问中等低跳跃访问数据敏感性敏感不敏感不敏感是否原地是否是关键结论快速排序平均最快因为它的分区操作是顺序扫描对 CPU 缓存友好。快速排序的最坏 O(n²)可通过随机化基准、三数取中、内省排序等优化避免。归并排序的稳定 最坏保证适合对稳定性有要求的场景。堆排序的O(1) 空间 最坏保证适合内存受限场景。各大语言的选择语言排序实现说明Cstd::sort 内省排序快排为主递归过深切堆排小数组切插入JavaArrays.sort基本类型 双轴快排对象数组用 Timsort归并插入Pythonsorted() Timsort归并插入的混合稳定Gosort.Slice 快排 插入 堆排类似内省排序7. 适用场景通用内存排序大多数场景下快排是首选速度最快。大规模随机数据平均 O(n log n)实际常数因子最小。对稳定性无要求如单纯数值排序。缓存敏感场景快排的顺序访问模式对 CPU 缓存友好。作为内省排序的核心Cstd::sort、Gosort.Slice的基础。Top-K 问题用快排的 partition 思想只需 O(n) 时间找到第 K 大元素QuickSelect 算法。
阅读完成 · 觉得有帮助？
