手写快速排序：从原理到应试技巧的完整指南

这类算法手写题最怕的不是写不出来而是写出来逻辑混乱、边界不清或者因为紧张导致关键步骤出错。快速排序作为面试和笔试中的高频考点很多人能背出代码但一到手写细节上就漏洞百出。这篇文章不讲快速排序的原理有多好而是直接聚焦在如何稳定、清晰、不出错地把它手写出来尤其适合准备技术面试、算法考试或者想巩固基础的程序员。我会从最容易被忽略的“应试”角度拆解告诉你手写时应该先写什么、怎么划分步骤、如何避免常见笔误以及如何向面试官展示你的思考过程。这些技巧能让你在有限时间和压力下依然能交出逻辑严谨、可运行的代码。1. 手写快速排序前先想清楚要展示什么很多人一拿到题目就开始埋头写partition函数这是最容易陷入混乱的开始。在手写场景下你的目标不是炫技而是清晰、正确、可解释。面试官或阅卷人看的是你的思维过程而不仅仅是最终代码。1.1 明确手写代码的评分点手写算法和机考不同没有编译器帮你查错。评分者通常会关注以下几个点逻辑完整性递归终止条件、分区过程、元素交换每一步都不能少。边界处理数组为空、只有一个元素、所有元素相等、已排序数组等边界情况是否考虑。代码清晰度变量命名、缩进、注释如果允许是否能让读者快速理解。关键步骤的注释或口头解释你能否在写代码的同时说出每一步在做什么。所以动笔前花10秒钟在脑子里过一下整个框架一个主递归函数quickSort一个核心分区函数partition。想清楚partition返回的是什么通常是基准值的最终位置以及递归时如何根据这个位置划分左右区间。1.2 选择最稳妥的实现版本快速排序有多种实现方式如 Lomuto 分区方案、Hoare 分区方案。对于手写我强烈建议使用经典的 Lomuto 分区方案。虽然它在处理大量重复元素时效率可能不是最优但它的逻辑极其清晰代码简短不易写错。Hoare 方案虽然原始且效率稍好但边界条件更微妙手写时容易出 bug。Lomuto 方案的核心特征选择最右元素作为基准pivot使用一个索引i来追踪“小于基准的区域”的边界。这个逻辑线性扫描一遍就能完成非常符合直觉。确定版本后就不要再犹豫。在考场上临时切换思路是手写大忌。2. 拆解手写步骤从框架到细节不要试图一气呵成。把手写过程分解成几个必然正确的步骤按顺序完成能极大降低出错率。2.1 第一步写出函数签名和递归框架这是最安全的第一步几乎不会错。先搭建好骨架。def quick_sort(arr, low, high): # 递归终止条件当区间有效时low high才进行排序 if low high: # 分区操作获取基准值位置 pi partition(arr, low, high) # 递归排序左半部分 quick_sort(arr, low, pi - 1) # 递归排序右半部分 quick_sort(arr, pi 1, high)为什么先写这个它定义了整个算法的递归结构一目了然。if low high:这个终止条件至关重要写在这里可以提醒自己不要忘记。它明确了partition函数的输入输出输入数组和区间输出基准值索引pi。2.2 第二步实现 Partition 函数Lomuto 方案这是快速排序的核心也是手写错误的高发区。按照固定流程来写def partition(arr, low, high): # 1. 选择基准值 (pivot) pivot arr[high] # 2. 初始化较小元素区域的边界索引 i i low - 1 # 3. 遍历区间 [low, high-1] for j in range(low, high): # 如果当前元素小于等于基准值 if arr[j] pivot: # 扩展较小元素区域 i 1 # 将当前元素交换到区域末尾 arr[i], arr[j] arr[j], arr[i] # 4. 将基准值放到正确位置 (i1) arr[i 1], arr[high] arr[high], arr[i 1] # 5. 返回基准值的最终位置 return i 1手写时逐行检查清单第3行i low - 1这是关键初始化i指向“小于等于pivot区域”的前一个位置。写成i low是常见错误。第5行for j in range(low, high):遍历范围是[low, high-1]因为arr[high]是基准值本身。务必注意区间是左闭右开(high不包含)。第7行if arr[j] pivot:使用是为了将等于基准值的元素也划到左侧这有助于在某些情况下获得更平衡的分区。如果写遇到重复元素时可能陷入低效递归。第12行arr[i 1], arr[high] arr[high], arr[i 1]循环结束后i1就是基准值该在的位置。这是最后一步交换千万别忘了。第14行return i 1返回的是基准值的新索引不是i。2.3 第三步编写一个简洁的驱动函数为了方便测试和展示可以写一个包装函数。这虽然不是必须的但能让你的代码更完整。def sort_array(arr): 对输入数组进行快速排序 if arr is None or len(arr) 1: return arr quick_sort(arr, 0, len(arr) - 1) return arr这个函数处理了输入为None或长度小于等于1的边界情况体现了你的健壮性思维。3. 手写过程中的关键技巧与避坑指南掌握了步骤还要注意书写时的细节这些细节决定了代码的“专业感”。3.1 变量命名与注释使用有意义的变量名low,high,pivot,i,j是约定俗成的不要随意改成left,right,x,y除非你非常确定。关键步骤添加简短注释在partition函数中在“选择基准值”、“初始化索引”、“遍历”、“交换”、“放置基准值”这几个步骤旁用//或#写一句话。这能有效引导阅卷人的视线展示你的逻辑。保持缩进一致手写时也要用明显的空格或制表符来表示代码块。混乱的缩进是扣分项。3.2 边界条件与特殊测试用例在手写时心里要默念几个测试用例确保你的代码能覆盖空数组[]你的驱动函数或初始调用应该直接返回。单元素数组[5]quick_sort中的if low high:条件会阻止进一步递归。已排序数组[1,2,3,4,5]Lomuto方案在这里会产生最坏情况分区每次只分出一个元素但代码逻辑必须正确。你可以口头说明这一点并提及优化方法如随机选择基准值。所有元素相等[7,7,7,7]if arr[j] pivot:中的确保了算法能正常工作。逆序数组[5,4,3,2,1]同样是测试最坏情况。一个重要的避坑点在quick_sort递归调用时区间是[low, pi-1]和[pi1, high]。千万不要写成[low, pi]和[pi, high]这会导致基准值被重复包含造成无限递归或错误结果。3.3 时间与空间复杂度分析手写代码后很可能被要求分析复杂度。提前准备好清晰的说法时间复杂度平均情况O(n log n)。每次分区大约将数组分成两半。最坏情况已排序/逆序O(n²)。但可以补充说明“通过随机选择基准值可以将最坏情况概率降到极低期望复杂度仍是 O(n log n)。”空间复杂度主要是递归调用栈的深度。平均情况O(log n)。最坏情况O(n)。手写时的小技巧如果允许可以在代码末尾或空白处用一两行字写下这些复杂度展示你的全面性。4. 从手写到口述如何应对面试追问手写代码只是开始面试官通常会针对你的代码提问。你的回答思路比答案本身更重要。4.1 如果被问到“为什么选择最右元素作为基准”不要只回答“简单”。可以这样组织语言 “我选择最右元素主要是为了代码实现的清晰和简洁。在手写场景下Lomuto分区方案结合最右基准值逻辑是线性的非常容易理解和验证。当然我也知道这种选择在输入已排序时会导致最坏情况。在实际工程中我们通常会采用随机选择基准值或者‘三数取中’法来避免这个问题显著提升性能的稳定性。”这个回答表明1. 你了解当前实现的优缺点2. 你知道工业级的优化方案。4.2 如果被问到“如何优化这段代码”这是展示你知识深度的好机会。可以分层次回答基准值选择优化随机选择 (pivot_index random.randint(low, high)) 或三数取中法。小数组优化当递归到子数组规模很小如长度 10时改用插入排序。因为插入排序在小数据量上常数因子更小。尾递归优化先递归处理较短的那部分区间以减少递归栈深度。处理大量重复元素介绍三路快速排序Dutch National Flag Problem将数组分成pivot,pivot,pivot三部分。手写时你可以说“在我的基础版本上可以通过这里、这里和这里进行优化……” 并用箭头或简单文字在代码旁标注。4.3 如果被要求“写一个非递归的快速排序”虽然不常见但值得准备。思路是用栈stack来模拟递归过程存储待排序的区间[low, high]。def quick_sort_iterative(arr): if len(arr) 1: return arr stack [(0, len(arr) - 1)] while stack: low, high stack.pop() if low high: pi partition(arr, low, high) # 将两个子区间压入栈先处理哪个都可以 # 为了模拟递归可以先压右区间再压左区间 stack.append((low, pi - 1)) stack.append((pi 1, high)) return arr关键在于理解栈存储的是“待处理的任务”。这个版本能避免递归过深导致的栈溢出但手写时要注意栈的操作顺序。5. 应试实战时间分配与检查策略在笔试或面试的白板编码环节时间有限需要策略。5.1 时间分配建议假设10分钟第1分钟审题确认是升序排序明确输入输出。在脑子里过一遍 Lomuto 分区步骤。第2-4分钟先写下quick_sort递归框架和partition函数骨架函数签名、关键变量定义。第5-7分钟填充partition函数的循环和交换逻辑。边写边小声念“i初始化为low-1j从low遍历到high-1如果arr[j]小于等于pivoti加1交换i和j...”第8分钟写驱动函数和简单的测试用例如[3,6,8,10,1,2,1]在脑子里或草稿上演算一遍。第9-10分钟从头到尾检查。重点检查递归终止条件if low high:。partition中i的初始值。for循环的边界。最后交换基准值的位置和返回值。递归调用区间是否正确。5.2 常见的笔误及快速检查方法死循环/栈溢出首先检查递归调用区间是否重叠必须是[low, pi-1]和[pi1, high]。排序结果不对用一个小数组如[3, 1, 2]在纸上手动模拟一遍你的partition过程。这是最快最有效的验证方法。漏掉元素检查for j in range(low, high):是否漏掉了high本身不应该包括以及初始i是否导致第一个元素被正确判断。最后保持代码整洁。如果写错了整齐地划掉重写比涂改成一团黑更清晰。手写快速排序稳定比炫技更重要。把上述步骤和检查点内化成习惯就能在压力下也能可靠地写出正确的代码。