1. 快速排序从“分而治之”到“原地排序”的核心思想快速排序这个名字听起来就带着一股“快刀斩乱麻”的利落劲儿。我第一次在算法书上看到它时觉得它简直是排序界的“魔法”——平均时间复杂度能达到 O(n log n)而且是在原地完成排序不需要像归并排序那样申请额外的数组空间。但真正动手实现尤其是处理各种边界条件时才发现这“魔法”背后全是扎实的逻辑和精巧的设计。它不像冒泡排序那样直观易懂也不像插入排序那样对近乎有序的数据有奇效但它在处理大规模、随机分布的通用数据时表现出的综合性能让它常年稳居“最常用排序算法”的宝座。简单来说快速排序解决的是如何高效地将一个无序数组变得有序的问题。它的核心策略是“分而治之”但和归并排序先分后治的思路不同快排是“边治边分”。它选择一个元素作为“基准”然后像一位经验丰富的调度员把数组重新排列让所有比基准小的元素都到它左边所有比基准大的元素都到它右边。这个过程完成后基准元素本身就已经处在了它最终排序后应该待的位置上。接下来我们只需要对基准左边和右边的两个子数组递归地重复这个过程直到子数组缩小到只有一个元素或为空整个数组自然就有序了。这个过程听起来简单但魔鬼藏在细节里。基准怎么选怎么高效地完成“小左大右”的划分递归的终止条件怎么写才不会栈溢出这些都是快排实现中的关键点也是面试和实际编码中经常考察的“坑点”。接下来我们就一层层剥开快排的“洋葱”看看它到底是怎么工作的以及如何写出一个既高效又健壮的快排实现。2. 核心原理与算法框架拆解2.1 “分治”策略的具象化分区操作快排的灵魂在于它的partition分区函数。这个函数的目标非常明确给定一个数组区间[left, right]选定一个基准值pivot经过一番操作后保证pivot左边的元素都不大于它假设我们按升序排序右边的元素都不小于它并且函数返回pivot最终所在位置的索引。想象一下你有一堆大小不一的石头要按重量从左到右排好。你可以先随手捡起一块石头作为“标尺”pivot然后开始整理把所有比这块轻的石头拨到左边比这块重的拨到右边。最后你把这块“标尺”石头放在轻石头区和重石头区的中间。现在这块“标尺”石头的位置就永远固定了因为它左边的都比它轻右边的都比它重它在整体排序中的位置已经确定。接下来你只需要分别对左边那堆和右边那堆石头重复同样的过程即可。在代码层面实现partition有多种经典方法最常用的是Lomuto 分区方案和Hoare 分区方案。Lomuto 方案逻辑清晰易于理解和实现是教学和入门时的首选而 Hoare 方案虽然逻辑稍复杂但交换次数更少在实际应用中通常效率更高。我们先从经典的 Lomuto 分区法讲起这是理解快排思想的最佳切入点。2.2 算法框架与递归驱动有了partition函数这个核心引擎快排的整体框架就非常简洁了它是一个典型的递归过程基准情况如果当前要排序的区间[left, right]的长度小于等于1即left right那么不需要排序直接返回。分区调用partition(arr, left, right)得到基准值pivot的最终位置pivot_index。递归对基准左侧的子数组[left, pivot_index - 1]递归调用快速排序。递归对基准右侧的子数组[pivot_index 1, right]递归调用快速排序。这个框架清晰地将“分治”思想代码化每一次partition解决一个元素的最终定位治并同时将原问题分解为两个规模更小的子问题分。递归的深度在理想情况下是 log₂n 层这也是快排平均时间复杂度优秀的根源。注意这里有一个非常重要的细节也是新手极易出错的地方。在递归调用时我们排的是[left, pivot_index - 1]和[pivot_index 1, right]一定不能包含pivot_index本身。因为经过partition操作后arr[pivot_index]已经处于其最终的正确位置无需再参与后续排序。如果错误地包含了它在某些情况下会导致无限递归或排序错误。3. 分区操作的两种经典实现详解3.1 Lomuto 分区法清晰易懂的教学版本Lomuto 分区法由 Nico Lomuto 提出它的思路非常直观像用一个指针i来维护一个“小于等于基准区”。我们通常选择当前区间最右边的元素arr[right]作为基准值pivot。初始化一个指针i left - 1。这个i指向的是“小于等于基准区”的最后一个元素。初始时这个区域是空的所以i在left的前面。使用另一个指针j从left遍历到right - 1因为right是基准。在遍历过程中如果发现arr[j] pivot说明这个元素应该属于“小于等于基准区”。那么我们就将i向右移动一位扩大该区域然后交换arr[i]和arr[j]。这样arr[i]及其左边的所有元素都是小于等于基准的。遍历结束后i指向的是“小于等于基准区”的最后一个元素。此时基准值pivot即arr[right]还在最右边。我们需要把它放到正确的位置也就是i 1的位置。所以交换arr[i 1]和arr[right]。最后返回i 1这就是基准值pivot的最终索引。def partition_lomuto(arr, left, right): Lomuto 分区方案 :param arr: 待排序数组 :param left: 区间左边界 :param right: 区间右边界 :return: 基准值最终位置的索引 # 选择最右边的元素作为基准 pivot arr[right] i left - 1 # 指向“小于等于区”的末尾 for j in range(left, right): # 遍历 left 到 right-1 if arr[j] pivot: i 1 # 扩大“小于等于区” arr[i], arr[j] arr[j], arr[i] # 将当前元素交换到该区域内 # 将基准值放到正确位置 arr[i 1], arr[right] arr[right], arr[i 1] return i 1Lomuto 分区的特点与坑点直观逻辑清晰容易理解和记忆。交换可能较多即使元素已经在正确的一侧也可能发生交换当i j时是自己和自己交换可以优化掉但逻辑上仍有一次赋值。对重复元素的处理由于条件是arr[j] pivot重复元素会被划到左侧这保证了算法的正确性但可能不是最平衡的划分。最坏情况如果每次都选到最大或最小的元素作为基准例如数组已升序或降序Lomuto分区会导致极度不平衡的划分时间复杂度退化为 O(n²)。这也是为什么需要“随机化”或“三数取中”等优化策略。3.2 Hoare 分区法效率更高的实践版本Hoare 分区法是快排发明者 Tony Hoare 最初提出的方法。它使用两个指针一个从左边向右扫描一个从右边向左扫描相向而行比 Lomuto 通常有更少的交换次数。选择基准值pivot。通常可以选择中间元素或者arr[left]。初始化两个指针i left - 1,j right 1。这样设计是为了让后续的do...while循环能正常工作。进入一个无限循环 a. 让i不断向右移动直到找到一个 pivot的元素。 b. 让j不断向左移动直到找到一个 pivot的元素。 c. 如果此时i j说明指针已经相遇或交叉分区完成返回j作为分界点。 d. 否则交换arr[i]和arr[j]然后继续循环。def partition_hoare(arr, left, right): Hoare 分区方案 :param arr: 待排序数组 :param left: 区间左边界 :param right: 区间右边界 :return: 分界点的索引 pivot arr[left] # 选择左端元素作为基准 i, j left - 1, right 1 while True: i 1 while arr[i] pivot: # 从左找第一个 pivot 的 i 1 j - 1 while arr[j] pivot: # 从右找第一个 pivot 的 j - 1 if i j: return j # 注意这里返回的是 j arr[i], arr[j] arr[j], arr[i]Hoare 分区的特点与坑点效率更高平均交换次数少于 Lomuto 方案。返回值的意义不同Hoare 分区返回的索引j其保证的是arr[left...j]中的元素都 pivot而arr[j1...right]中的元素都 pivot。但arr[j]本身并不一定是基准值pivot。这是与 Lomuto 最大的区别。递归区间的划分由于上述区别在使用 Hoare 分区时递归调用应写为quick_sort(arr, left, p)和quick_sort(arr, p1, right)其中p是partition_hoare的返回值。这个边界处理需要格外小心。循环条件内层while循环必须防止数组越界但上面简化的代码假设了pivot一定在数组中且不会所有元素都相同导致指针无限移动。在生产代码中需要增加i right和j left的边界检查。实操心得选哪个对于学习和面试务必掌握Lomuto 分区法因为它逻辑直白边界清晰是阐述快排思想的最佳载体。对于追求性能的实际项目或竞赛Hoare 分区法是更好的选择但你必须非常清楚其边界条件的处理逻辑否则极易写出死循环或错误的代码。我个人的习惯是在需要快速实现一个正确的快排时用 Lomuto在性能关键的模块中会仔细实现并测试 Hoare 方案。4. 从零实现一个健壮的快速排序理解了分区原理我们就可以组装出一个完整的快速排序函数了。这里我们以 Lomuto 分区为例因为它递归部分的边界处理更符合直觉。4.1 基础版本实现def quick_sort_basic(arr, left, right): 快速排序基础版本 (使用 Lomuto 分区) # 递归终止条件区间内元素少于2个 if left right: return # 分区操作获取基准位置 pivot_index partition_lomuto(arr, left, right) # 递归排序左半部分 quick_sort_basic(arr, left, pivot_index - 1) # 递归排序右半部分 quick_sort_basic(arr, pivot_index 1, right) # 为了方便调用可以封装一个包装函数 def sort_array_basic(arr): if not arr or len(arr) 2: return arr quick_sort_basic(arr, 0, len(arr) - 1) return arr这个版本已经可以正确排序了。但是它有一个致命弱点对已经有序或逆序的数组性能会急剧下降。考虑一个已经升序排列的数组[1, 2, 3, 4, 5]如果总是选择最右边的元素作为基准Lomuto的默认策略那么每次分区后左子区间都包含了n-1个元素右子区间为空。递归树退化成一个深度为n的链时间复杂度变为 O(n²)而且递归调用深度也达到n对于大数组可能导致栈溢出。4.2 关键优化随机化与三数取中为了解决上述最坏情况核心在于优化基准pivot的选择策略让划分尽可能均衡。随机化在分区前随机从[left, right]区间中选一个元素与arr[right]交换然后再以arr[right]为基准进行标准的 Lomuto 分区。这样即使输入数组是有序的由于基准是随机的算法退化的概率也变得极低。import random def partition_lomuto_random(arr, left, right): # 随机选择一个下标 random_index random.randint(left, right) # 将随机选中的元素交换到最右边作为基准 arr[random_index], arr[right] arr[right], arr[random_index] # 后续与标准 Lomuto 分区完全相同 pivot arr[right] i left - 1 for j in range(left, right): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[right] arr[right], arr[i 1] return i 1三数取中另一种更稳定不依赖随机数的方法是取区间头、尾、中间三个元素的中位数作为基准。这能有效避免在已部分有序的数组上出现极端划分。def get_median_of_three(arr, left, right): mid left (right - left) // 2 a, b, c arr[left], arr[mid], arr[right] # 找出 a, b, c 的中值 if a b c or c b a: return mid elif b a c or c a b: return left else: return right def partition_lomuto_mot(arr, left, right): median_index get_median_of_three(arr, left, right) arr[median_index], arr[right] arr[right], arr[median_index] # 后续与标准 Lomuto 分区完全相同 pivot arr[right] i left - 1 for j in range(left, right): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[right] arr[right], arr[i 1] return i 1实操心得优化策略的选择在实际项目中我通常会优先使用“随机化”。理由很简单实现容易且能以极高的概率避免最坏情况对于通用数据足够好。“三数取中”在确定性环境中比如某些对随机数敏感的嵌入式系统或需要完全可重复的测试场景是更好的选择它提供了更稳定的性能保证。可以将两者结合先三数取中如果取到的中位数恰好是端点再考虑随机化但这通常有些过度设计。对于绝大多数应用随机化 Lomuto 分区已经是一个非常优秀的起点。4.3 进一步优化处理小数组与重复元素小数组优化当递归到子数组规模很小比如长度小于 10 或 20时快速排序的递归开销和函数调用成本可能比算法本身的优势更突出。此时可以切换到插入排序这类对小数据量高效的简单排序算法。这是一个经典的优化手段。def quick_sort_optimized(arr, left, right): # 小数组使用插入排序 if right - left 1 10: # 阈值可调整常用 10-20 insertion_sort(arr, left, right) return pivot_index partition_lomuto_random(arr, left, right) quick_sort_optimized(arr, left, pivot_index - 1) quick_sort_optimized(arr, pivot_index 1, right)三路快速排序当数组中存在大量重复元素时标准的二路快排只分小于等于和大于两个区仍然会进行很多不必要的递归和交换。三路快排将数组分为三部分小于基准、等于基准、大于基准。这样在一次分区后所有等于基准的元素都一次性归位不再参与后续递归能极大提升包含大量重复元素数组的排序速度。def quick_sort_3way(arr, left, right): if left right: return # 随机化基准 random_index random.randint(left, right) arr[left], arr[random_index] arr[random_index], arr[left] pivot arr[left] lt left # lt 指向小于区的末尾 gt right # gt 指向大于区的开头 i left 1 # i 是当前遍历指针 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 # 注意这里 i 不增加因为从 gt 换过来的元素还未检查 else: # arr[i] pivot i 1 # 循环结束后arr[left...lt-1] pivot, arr[lt...gt] pivot, arr[gt1...right] pivot quick_sort_3way(arr, left, lt - 1) quick_sort_3way(arr, gt 1, right)5. 性能分析、常见问题与避坑指南5.1 时间复杂度与空间复杂度平均时间复杂度O(n log n)。这是快排表现出色的原因在随机化优化下这是它的期望时间复杂度。最坏时间复杂度O(n²)。当每次分区都极度不平衡例如总是选到最小或最大值作为基准时发生。随机化或三数取中优化正是为了将出现这种情况的概率降到极低。最好时间复杂度O(n log n)。每次分区都几乎平衡时达到。空间复杂度主要是递归调用栈所占用的空间。平均情况下递归深度为 O(log n)故平均空间复杂度为 O(log n)。最坏情况下未优化递归深度为 O(n)空间复杂度也为 O(n)。优化后最坏情况概率极低。5.2 稳定性分析快速排序不是稳定的排序算法。稳定性是指相等的元素在排序后其相对顺序保持不变。在快排的分区过程中元素会因与基准的比较而发生跨区域的交换这很容易打乱相等元素的原始顺序。例如对[(3, a), (2, b), (3, c)]按数字排序两个3的相对顺序(a, c)可能在排序后变成(c, a)。如果业务需要稳定性应选择归并排序或插入排序。5.3 常见问题与排查技巧实录问题1栈溢出错误 (RecursionError: maximum recursion depth exceeded)现象对大型数组排序时程序崩溃。原因未进行基准选择优化对已排序数组排序导致递归深度达到 n。递归终止条件写错例如写成了if left right但初始调用时left0, rightlen(arr)-1可能因数组为空而出错或者漏掉了号导致无限递归。递归区间划分错误特别是使用 Hoare 分区时错误地将基准索引包含进了子区间。排查与解决强制优化务必使用随机化或三数取中选择基准。检查终止条件确认是if left right。可以增加打印语句观察递归深度和区间变化。小数组优化当区间长度小于某个阈值如15时切换到非递归的插入排序这能显著减少深层递归调用。改为迭代使用栈来模拟递归过程实现非递归版本的快排彻底避免递归深度限制。问题2排序结果不正确现象数组没有完全排序或顺序混乱。原因分区函数逻辑错误这是最常见的原因。仔细检查指针移动和交换的条件。对于 Lomuto检查if arr[j] pivot中的是否写成了会导致等于基准的元素被错误处理。基准值选择后未交换在使用随机化或三数取中时记得将选中的基准值交换到分区函数预期的位置如 Lomuto 的right位置。递归区间错误这是第二大常见原因。确保左区间是[left, pivot_index-1]右区间是[pivot_index1, right]。一个记忆技巧基准元素在pivot_index它已经排好所以两边都要排除它。数组边界处理在分区循环中确保指针不会越界。特别是在 Hoare 分区中内层while循环要加上i right和j left的条件。排查与解决单元测试用各种边界用例测试你的分区函数空数组、单元素数组、已排序数组、逆序数组、全等数组、包含重复元素的随机数组。打印调试在分区前后打印数组状态和返回的索引手动验证划分是否正确。使用已知正确的代码对比用一个简单的、正确但低效的排序算法如冒泡排序作为基准比较两者的输出。问题3对大量重复元素排序效率低下现象数组中有很多相同值标准快排跑得很慢。原因标准二路快排会把所有等于基准的元素都放到一边如果重复元素很多会导致分区极度不平衡。解决实现三路快速排序。它能将等于基准的元素集中放在中间一次性地将它们排除在后续递归之外对含大量重复元素的数组性能提升非常显著。问题4如何选择分区方案面试与学习用Lomuto。逻辑清晰易于在白板上写对是沟通想法的好工具。追求性能用Hoare。平均交换次数更少。但务必厘清其返回值的含义和递归边界[left, p]和[p1, right]。大量重复数据用三路快排。这是针对此类数据的最优变种。快速排序的魅力在于其简洁而强大的思想以及为了将这种思想在复杂现实中完美实现所需的各种精细处理。从理解“分治”开始到掌握分区再到处理边界、优化性能每一步都充满了编程的乐趣和挑战。我自己的经验是不要死记硬背代码而是理解每一个if判断、每一次指针移动背后的意图。当你能够清晰地解释为什么递归区间要排除基准索引为什么随机化能避免最坏情况时你才算真正掌握了快排。下次当你需要排序时不妨先想想快排然后根据数据特点选择合适的优化策略亲手实现它。 
长河君 · 2026/8/7 12:08:21 · 阅读 1.2k 快速排序算法详解：从分治思想到工程优化实现
1. 快速排序从“分而治之”到“原地排序”的核心思想快速排序这个名字听起来就带着一股“快刀斩乱麻”的利落劲儿。我第一次在算法书上看到它时觉得它简直是排序界的“魔法”——平均时间复杂度能达到 O(n log n)而且是在原地完成排序不需要像归并排序那样申请额外的数组空间。但真正动手实现尤其是处理各种边界条件时才发现这“魔法”背后全是扎实的逻辑和精巧的设计。它不像冒泡排序那样直观易懂也不像插入排序那样对近乎有序的数据有奇效但它在处理大规模、随机分布的通用数据时表现出的综合性能让它常年稳居“最常用排序算法”的宝座。简单来说快速排序解决的是如何高效地将一个无序数组变得有序的问题。它的核心策略是“分而治之”但和归并排序先分后治的思路不同快排是“边治边分”。它选择一个元素作为“基准”然后像一位经验丰富的调度员把数组重新排列让所有比基准小的元素都到它左边所有比基准大的元素都到它右边。这个过程完成后基准元素本身就已经处在了它最终排序后应该待的位置上。接下来我们只需要对基准左边和右边的两个子数组递归地重复这个过程直到子数组缩小到只有一个元素或为空整个数组自然就有序了。这个过程听起来简单但魔鬼藏在细节里。基准怎么选怎么高效地完成“小左大右”的划分递归的终止条件怎么写才不会栈溢出这些都是快排实现中的关键点也是面试和实际编码中经常考察的“坑点”。接下来我们就一层层剥开快排的“洋葱”看看它到底是怎么工作的以及如何写出一个既高效又健壮的快排实现。2. 核心原理与算法框架拆解2.1 “分治”策略的具象化分区操作快排的灵魂在于它的partition分区函数。这个函数的目标非常明确给定一个数组区间[left, right]选定一个基准值pivot经过一番操作后保证pivot左边的元素都不大于它假设我们按升序排序右边的元素都不小于它并且函数返回pivot最终所在位置的索引。想象一下你有一堆大小不一的石头要按重量从左到右排好。你可以先随手捡起一块石头作为“标尺”pivot然后开始整理把所有比这块轻的石头拨到左边比这块重的拨到右边。最后你把这块“标尺”石头放在轻石头区和重石头区的中间。现在这块“标尺”石头的位置就永远固定了因为它左边的都比它轻右边的都比它重它在整体排序中的位置已经确定。接下来你只需要分别对左边那堆和右边那堆石头重复同样的过程即可。在代码层面实现partition有多种经典方法最常用的是Lomuto 分区方案和Hoare 分区方案。Lomuto 方案逻辑清晰易于理解和实现是教学和入门时的首选而 Hoare 方案虽然逻辑稍复杂但交换次数更少在实际应用中通常效率更高。我们先从经典的 Lomuto 分区法讲起这是理解快排思想的最佳切入点。2.2 算法框架与递归驱动有了partition函数这个核心引擎快排的整体框架就非常简洁了它是一个典型的递归过程基准情况如果当前要排序的区间[left, right]的长度小于等于1即left right那么不需要排序直接返回。分区调用partition(arr, left, right)得到基准值pivot的最终位置pivot_index。递归对基准左侧的子数组[left, pivot_index - 1]递归调用快速排序。递归对基准右侧的子数组[pivot_index 1, right]递归调用快速排序。这个框架清晰地将“分治”思想代码化每一次partition解决一个元素的最终定位治并同时将原问题分解为两个规模更小的子问题分。递归的深度在理想情况下是 log₂n 层这也是快排平均时间复杂度优秀的根源。注意这里有一个非常重要的细节也是新手极易出错的地方。在递归调用时我们排的是[left, pivot_index - 1]和[pivot_index 1, right]一定不能包含pivot_index本身。因为经过partition操作后arr[pivot_index]已经处于其最终的正确位置无需再参与后续排序。如果错误地包含了它在某些情况下会导致无限递归或排序错误。3. 分区操作的两种经典实现详解3.1 Lomuto 分区法清晰易懂的教学版本Lomuto 分区法由 Nico Lomuto 提出它的思路非常直观像用一个指针i来维护一个“小于等于基准区”。我们通常选择当前区间最右边的元素arr[right]作为基准值pivot。初始化一个指针i left - 1。这个i指向的是“小于等于基准区”的最后一个元素。初始时这个区域是空的所以i在left的前面。使用另一个指针j从left遍历到right - 1因为right是基准。在遍历过程中如果发现arr[j] pivot说明这个元素应该属于“小于等于基准区”。那么我们就将i向右移动一位扩大该区域然后交换arr[i]和arr[j]。这样arr[i]及其左边的所有元素都是小于等于基准的。遍历结束后i指向的是“小于等于基准区”的最后一个元素。此时基准值pivot即arr[right]还在最右边。我们需要把它放到正确的位置也就是i 1的位置。所以交换arr[i 1]和arr[right]。最后返回i 1这就是基准值pivot的最终索引。def partition_lomuto(arr, left, right): Lomuto 分区方案 :param arr: 待排序数组 :param left: 区间左边界 :param right: 区间右边界 :return: 基准值最终位置的索引 # 选择最右边的元素作为基准 pivot arr[right] i left - 1 # 指向“小于等于区”的末尾 for j in range(left, right): # 遍历 left 到 right-1 if arr[j] pivot: i 1 # 扩大“小于等于区” arr[i], arr[j] arr[j], arr[i] # 将当前元素交换到该区域内 # 将基准值放到正确位置 arr[i 1], arr[right] arr[right], arr[i 1] return i 1Lomuto 分区的特点与坑点直观逻辑清晰容易理解和记忆。交换可能较多即使元素已经在正确的一侧也可能发生交换当i j时是自己和自己交换可以优化掉但逻辑上仍有一次赋值。对重复元素的处理由于条件是arr[j] pivot重复元素会被划到左侧这保证了算法的正确性但可能不是最平衡的划分。最坏情况如果每次都选到最大或最小的元素作为基准例如数组已升序或降序Lomuto分区会导致极度不平衡的划分时间复杂度退化为 O(n²)。这也是为什么需要“随机化”或“三数取中”等优化策略。3.2 Hoare 分区法效率更高的实践版本Hoare 分区法是快排发明者 Tony Hoare 最初提出的方法。它使用两个指针一个从左边向右扫描一个从右边向左扫描相向而行比 Lomuto 通常有更少的交换次数。选择基准值pivot。通常可以选择中间元素或者arr[left]。初始化两个指针i left - 1,j right 1。这样设计是为了让后续的do...while循环能正常工作。进入一个无限循环 a. 让i不断向右移动直到找到一个 pivot的元素。 b. 让j不断向左移动直到找到一个 pivot的元素。 c. 如果此时i j说明指针已经相遇或交叉分区完成返回j作为分界点。 d. 否则交换arr[i]和arr[j]然后继续循环。def partition_hoare(arr, left, right): Hoare 分区方案 :param arr: 待排序数组 :param left: 区间左边界 :param right: 区间右边界 :return: 分界点的索引 pivot arr[left] # 选择左端元素作为基准 i, j left - 1, right 1 while True: i 1 while arr[i] pivot: # 从左找第一个 pivot 的 i 1 j - 1 while arr[j] pivot: # 从右找第一个 pivot 的 j - 1 if i j: return j # 注意这里返回的是 j arr[i], arr[j] arr[j], arr[i]Hoare 分区的特点与坑点效率更高平均交换次数少于 Lomuto 方案。返回值的意义不同Hoare 分区返回的索引j其保证的是arr[left...j]中的元素都 pivot而arr[j1...right]中的元素都 pivot。但arr[j]本身并不一定是基准值pivot。这是与 Lomuto 最大的区别。递归区间的划分由于上述区别在使用 Hoare 分区时递归调用应写为quick_sort(arr, left, p)和quick_sort(arr, p1, right)其中p是partition_hoare的返回值。这个边界处理需要格外小心。循环条件内层while循环必须防止数组越界但上面简化的代码假设了pivot一定在数组中且不会所有元素都相同导致指针无限移动。在生产代码中需要增加i right和j left的边界检查。实操心得选哪个对于学习和面试务必掌握Lomuto 分区法因为它逻辑直白边界清晰是阐述快排思想的最佳载体。对于追求性能的实际项目或竞赛Hoare 分区法是更好的选择但你必须非常清楚其边界条件的处理逻辑否则极易写出死循环或错误的代码。我个人的习惯是在需要快速实现一个正确的快排时用 Lomuto在性能关键的模块中会仔细实现并测试 Hoare 方案。4. 从零实现一个健壮的快速排序理解了分区原理我们就可以组装出一个完整的快速排序函数了。这里我们以 Lomuto 分区为例因为它递归部分的边界处理更符合直觉。4.1 基础版本实现def quick_sort_basic(arr, left, right): 快速排序基础版本 (使用 Lomuto 分区) # 递归终止条件区间内元素少于2个 if left right: return # 分区操作获取基准位置 pivot_index partition_lomuto(arr, left, right) # 递归排序左半部分 quick_sort_basic(arr, left, pivot_index - 1) # 递归排序右半部分 quick_sort_basic(arr, pivot_index 1, right) # 为了方便调用可以封装一个包装函数 def sort_array_basic(arr): if not arr or len(arr) 2: return arr quick_sort_basic(arr, 0, len(arr) - 1) return arr这个版本已经可以正确排序了。但是它有一个致命弱点对已经有序或逆序的数组性能会急剧下降。考虑一个已经升序排列的数组[1, 2, 3, 4, 5]如果总是选择最右边的元素作为基准Lomuto的默认策略那么每次分区后左子区间都包含了n-1个元素右子区间为空。递归树退化成一个深度为n的链时间复杂度变为 O(n²)而且递归调用深度也达到n对于大数组可能导致栈溢出。4.2 关键优化随机化与三数取中为了解决上述最坏情况核心在于优化基准pivot的选择策略让划分尽可能均衡。随机化在分区前随机从[left, right]区间中选一个元素与arr[right]交换然后再以arr[right]为基准进行标准的 Lomuto 分区。这样即使输入数组是有序的由于基准是随机的算法退化的概率也变得极低。import random def partition_lomuto_random(arr, left, right): # 随机选择一个下标 random_index random.randint(left, right) # 将随机选中的元素交换到最右边作为基准 arr[random_index], arr[right] arr[right], arr[random_index] # 后续与标准 Lomuto 分区完全相同 pivot arr[right] i left - 1 for j in range(left, right): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[right] arr[right], arr[i 1] return i 1三数取中另一种更稳定不依赖随机数的方法是取区间头、尾、中间三个元素的中位数作为基准。这能有效避免在已部分有序的数组上出现极端划分。def get_median_of_three(arr, left, right): mid left (right - left) // 2 a, b, c arr[left], arr[mid], arr[right] # 找出 a, b, c 的中值 if a b c or c b a: return mid elif b a c or c a b: return left else: return right def partition_lomuto_mot(arr, left, right): median_index get_median_of_three(arr, left, right) arr[median_index], arr[right] arr[right], arr[median_index] # 后续与标准 Lomuto 分区完全相同 pivot arr[right] i left - 1 for j in range(left, right): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[right] arr[right], arr[i 1] return i 1实操心得优化策略的选择在实际项目中我通常会优先使用“随机化”。理由很简单实现容易且能以极高的概率避免最坏情况对于通用数据足够好。“三数取中”在确定性环境中比如某些对随机数敏感的嵌入式系统或需要完全可重复的测试场景是更好的选择它提供了更稳定的性能保证。可以将两者结合先三数取中如果取到的中位数恰好是端点再考虑随机化但这通常有些过度设计。对于绝大多数应用随机化 Lomuto 分区已经是一个非常优秀的起点。4.3 进一步优化处理小数组与重复元素小数组优化当递归到子数组规模很小比如长度小于 10 或 20时快速排序的递归开销和函数调用成本可能比算法本身的优势更突出。此时可以切换到插入排序这类对小数据量高效的简单排序算法。这是一个经典的优化手段。def quick_sort_optimized(arr, left, right): # 小数组使用插入排序 if right - left 1 10: # 阈值可调整常用 10-20 insertion_sort(arr, left, right) return pivot_index partition_lomuto_random(arr, left, right) quick_sort_optimized(arr, left, pivot_index - 1) quick_sort_optimized(arr, pivot_index 1, right)三路快速排序当数组中存在大量重复元素时标准的二路快排只分小于等于和大于两个区仍然会进行很多不必要的递归和交换。三路快排将数组分为三部分小于基准、等于基准、大于基准。这样在一次分区后所有等于基准的元素都一次性归位不再参与后续递归能极大提升包含大量重复元素数组的排序速度。def quick_sort_3way(arr, left, right): if left right: return # 随机化基准 random_index random.randint(left, right) arr[left], arr[random_index] arr[random_index], arr[left] pivot arr[left] lt left # lt 指向小于区的末尾 gt right # gt 指向大于区的开头 i left 1 # i 是当前遍历指针 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 # 注意这里 i 不增加因为从 gt 换过来的元素还未检查 else: # arr[i] pivot i 1 # 循环结束后arr[left...lt-1] pivot, arr[lt...gt] pivot, arr[gt1...right] pivot quick_sort_3way(arr, left, lt - 1) quick_sort_3way(arr, gt 1, right)5. 性能分析、常见问题与避坑指南5.1 时间复杂度与空间复杂度平均时间复杂度O(n log n)。这是快排表现出色的原因在随机化优化下这是它的期望时间复杂度。最坏时间复杂度O(n²)。当每次分区都极度不平衡例如总是选到最小或最大值作为基准时发生。随机化或三数取中优化正是为了将出现这种情况的概率降到极低。最好时间复杂度O(n log n)。每次分区都几乎平衡时达到。空间复杂度主要是递归调用栈所占用的空间。平均情况下递归深度为 O(log n)故平均空间复杂度为 O(log n)。最坏情况下未优化递归深度为 O(n)空间复杂度也为 O(n)。优化后最坏情况概率极低。5.2 稳定性分析快速排序不是稳定的排序算法。稳定性是指相等的元素在排序后其相对顺序保持不变。在快排的分区过程中元素会因与基准的比较而发生跨区域的交换这很容易打乱相等元素的原始顺序。例如对[(3, a), (2, b), (3, c)]按数字排序两个3的相对顺序(a, c)可能在排序后变成(c, a)。如果业务需要稳定性应选择归并排序或插入排序。5.3 常见问题与排查技巧实录问题1栈溢出错误 (RecursionError: maximum recursion depth exceeded)现象对大型数组排序时程序崩溃。原因未进行基准选择优化对已排序数组排序导致递归深度达到 n。递归终止条件写错例如写成了if left right但初始调用时left0, rightlen(arr)-1可能因数组为空而出错或者漏掉了号导致无限递归。递归区间划分错误特别是使用 Hoare 分区时错误地将基准索引包含进了子区间。排查与解决强制优化务必使用随机化或三数取中选择基准。检查终止条件确认是if left right。可以增加打印语句观察递归深度和区间变化。小数组优化当区间长度小于某个阈值如15时切换到非递归的插入排序这能显著减少深层递归调用。改为迭代使用栈来模拟递归过程实现非递归版本的快排彻底避免递归深度限制。问题2排序结果不正确现象数组没有完全排序或顺序混乱。原因分区函数逻辑错误这是最常见的原因。仔细检查指针移动和交换的条件。对于 Lomuto检查if arr[j] pivot中的是否写成了会导致等于基准的元素被错误处理。基准值选择后未交换在使用随机化或三数取中时记得将选中的基准值交换到分区函数预期的位置如 Lomuto 的right位置。递归区间错误这是第二大常见原因。确保左区间是[left, pivot_index-1]右区间是[pivot_index1, right]。一个记忆技巧基准元素在pivot_index它已经排好所以两边都要排除它。数组边界处理在分区循环中确保指针不会越界。特别是在 Hoare 分区中内层while循环要加上i right和j left的条件。排查与解决单元测试用各种边界用例测试你的分区函数空数组、单元素数组、已排序数组、逆序数组、全等数组、包含重复元素的随机数组。打印调试在分区前后打印数组状态和返回的索引手动验证划分是否正确。使用已知正确的代码对比用一个简单的、正确但低效的排序算法如冒泡排序作为基准比较两者的输出。问题3对大量重复元素排序效率低下现象数组中有很多相同值标准快排跑得很慢。原因标准二路快排会把所有等于基准的元素都放到一边如果重复元素很多会导致分区极度不平衡。解决实现三路快速排序。它能将等于基准的元素集中放在中间一次性地将它们排除在后续递归之外对含大量重复元素的数组性能提升非常显著。问题4如何选择分区方案面试与学习用Lomuto。逻辑清晰易于在白板上写对是沟通想法的好工具。追求性能用Hoare。平均交换次数更少。但务必厘清其返回值的含义和递归边界[left, p]和[p1, right]。大量重复数据用三路快排。这是针对此类数据的最优变种。快速排序的魅力在于其简洁而强大的思想以及为了将这种思想在复杂现实中完美实现所需的各种精细处理。从理解“分治”开始到掌握分区再到处理边界、优化性能每一步都充满了编程的乐趣和挑战。我自己的经验是不要死记硬背代码而是理解每一个if判断、每一次指针移动背后的意图。当你能够清晰地解释为什么递归区间要排除基准索引为什么随机化能避免最坏情况时你才算真正掌握了快排。下次当你需要排序时不妨先想想快排然后根据数据特点选择合适的优化策略亲手实现它。