从一道OJ题看快排的“坑”：为什么你的排序结果和样例对不上？详解边界与输出细节

从一道OJ题看快排的“坑”为什么你的排序结果和样例对不上详解边界与输出细节在算法竞赛和面试中快速排序是最常考察的排序算法之一。表面上看它逻辑清晰、实现简单但当你真正动手实现时却可能遇到各种意想不到的问题——特别是当题目要求输出每趟排序的中间结果时。很多人在这种情况下会发现自己的代码虽然能正确排序但输出却和题目样例对不上。这背后隐藏着哪些容易被忽视的细节1. 理解题目特殊要求为什么标准快排不够用大多数教材和教程展示的快排实现都是“标准版”——只关注最终排序结果不关心中间过程。但在OJ题目中经常会有类似“输出每趟排序结果”的要求这就需要对标准实现进行改造。以本题为例关键要求有两点每次交换后立即输出整个数组这与标准快排的实现逻辑有本质区别长度为1的子序列不用输出这会影响递归终止条件的处理考虑标准快排的划分函数int partition(int arr[], int low, int high) { int pivot arr[low]; while(low high) { while(low high arr[high] pivot) high--; arr[low] arr[high]; while(low high arr[low] pivot) low; arr[high] arr[low]; } arr[low] pivot; return low; }而题目要求的实现需要在每次交换后输出int qsort2(int low, int high) { int key zu[low]; while(low high) { while(low high key zu[high]) high--; swap(zu[low], zu[high]); show(); // 关键区别每次交换后立即输出 while(low high key zu[low]) low; swap(zu[low], zu[high]); show(); // 关键区别每次交换后立即输出 } return low; }2. 输出时机的陷阱为什么会有“重复”输出仔细对比题目样例的输出你会发现有些行看起来是“重复”的55 22 6 111 333 444 6 22 55 111 333 444 6 22 55 111 333 444 6 22 55 111 333 444这其实反映了快排的执行过程第一次交换后55和111交换基准值归位后6和55交换进入递归前数组状态稳定关键点题目要求的是“每次交换后”输出而不是“每趟排序后”输出。这意味着一次完整的划分过程可能产生多次输出基准值最终归位时也会产生输出递归调用前的数组状态也会输出3. 边界条件处理为什么n1时要特殊处理题目明确要求“长度为1的子序列不用排不用输出”。这直接影响两个地方的处理主函数中的特殊判断if(n 1) break; // 跳过长度为1的情况递归终止条件void qsort1(int low, int high) { if(low high) { // 确保子序列长度1才处理 int zhou qsort2(low, high); qsort1(low, zhou-1); qsort1(zhou1, high); } }如果不做这些处理当n1时可能输出不应该出现的单元素序列或者导致不必要的函数调用开销4. 常见错误与调试技巧在实际编码中容易犯的错误主要有三类4.1 输出时机错误错误表现只在基准值归位时输出一次或者只在递归调用前输出正确做法每次swap后立即调用show()包括基准值移动过程中的所有交换4.2 递归边界处理不当错误表现对长度为1的子序列也输出递归终止条件写成low high调试技巧// 添加调试输出 void qsort1(int low, int high) { cout Processing: low to high endl; if(low high) { // ... } }4.3 输出格式问题易错点最后一个数字后面有多余空格测试用例之间缺少空行正确输出函数void show() { for(int i 0; i n; i) { cout zu[i]; if(i ! n-1) cout ; // 控制空格 } cout endl; // 记得换行 }5. 从这道题中学到的快排本质这道题的价值在于它强迫我们关注快排的每个细节动作而不只是最终结果。通过这道题我们可以更深入地理解快排是不稳定的交换顺序会影响中间输出基准值的选择影响过程第一个元素作为基准是最常见的实现递归的精确控制确保每次只处理长度1的子序列对于面试准备建议在理解标准实现的基础上尝试改造实现以满足各种可能的变种要求。这才是真正掌握算法的表现。