先说一句掏心窝的话这道题我在课程作业、面试手写代码、甚至帮人改代码时都见过无数次。“C语言实现快速排序以第一个元素作为枢轴”听起来像教科书里最经典的开篇案例可真正动手写的时候大多数人卡在了同一个地方——单趟划分的指针移动顺序和边界条件。网上代码一搜一大把但能讲清楚为什么这么写、哪里容易翻车的真不多。这篇文章我不打算只丢一段能跑的代码给你。我会把“以第一个元素作为枢轴”这件事拆开揉碎从核心思路、单趟划分手推过程、完整C代码实现到最容易被忽略的性能退化问题再到我实际调试中踩过的坑一次性讲透。不管你是正在学数据结构的学生、准备算法面试的开发者还是想把这个经典写法真正吃透的C语言爱好者都能在这里找到你需要的东西。1. 这个题到底在考什么1.1 快速排序的核心思想一句话就能说清快速排序Quick Sort是典型的分治Divide and Conquer算法。它的核心思路其实特别朴素从待排序区间里挑一个元素把它当作“枢轴”pivot然后把剩下的元素分成两拨比枢轴小的放到它左边比枢轴大的放到它右边。这样一来枢轴元素就落在了它最终应该在的位置上。接下来就简单了枢轴左边的子区间和右边的子区间分别再做同样的事情递归下去。直到子区间里只剩一个元素或者空排序就结束了。这个过程有个特别直观的类比想象你是一群人的组织者你随机点名一个人当“标杆”然后让所有比他矮的人站到他左边所有比他高的人站到他右边。现在标杆的位置已经对了剩下要做的事情就是让左边那一堆人再重复这个动作右边那一堆人也重复这个动作。每一轮都在“归位”一个标杆递归下去所有人就都站好了。1.2 为什么题目偏偏指定“第一个元素当枢轴”“以第一个元素作为枢轴”这个要求很多人不理解觉得这不是很蠢吗如果数组本来就是有序的第一个元素当枢轴岂不是每次都把区间切成长度1和长度n-1这样极端不对称的两部分这里要分两层看。第一层教学和考试场景里这个指定是为了让算法的步骤“可预期”。不管你输入什么数组第一个元素是谁划分规则就是固定的这样老师可以手推步骤、出题考过程学生也容易验证自己写的代码对不对。它牺牲了一部分性能上的聪明劲儿换来了清晰和简单。第二层才是真正值得你记住的它暴露了“固定选枢轴”这一策略的天然缺陷。这种缺陷在工程上是致命的但在学习阶段却非常有价值——它逼你去思考为什么工业级的快速排序实现比如很多标准库里的排序函数都不会死板地用第一个元素当枢轴而是要加随机化或者三数取中。理解了这一点你才算真正把快速排序学透了而不只是背代码。我先说结论后面会专门用一整节来展开如果数组恰好是正序或逆序固定选第一个元素会导致快速排序退化成“慢速排序”时间复杂度从平均的O(n log n)直接掉到O(n²)。这不是危言耸听我实测过10000个有序整数排序耗时和10000个随机整数差了两个数量级。2. 单趟划分整个算法的灵魂2.1 挖坑法双指针的动态过程以第一个元素作为枢轴的实现方式里我个人最推荐的是“挖坑法”也叫挖坑填数法。原因很简单它把元素交换的动作变成了“挖坑”和“填坑”的交替移动对初学者来说极为直观也特别不容易在细节上出错。先把第一个元素的值用一个变量pivot保存起来。取出这个值之后在数组逻辑上就出现了一个“坑”它在最左边。接下来安排两个指针i指向左边界也就是坑的位置j指向右边界。规则就两条j从右往左走找到一个比pivot小的元素。找到了把它填到i当前的坑里。填完之后j的位置就变成了新的坑。i从左往右走找到一个比pivot大的元素。找到了把它填到j当前的坑里。填完之后i的位置又变成了新的坑。如此循环往复i和j互相往中间靠拢不停“填坑—产生新坑”。直到i和j相遇这个位置就是pivot的最终归宿把pivot填进去单趟划分就结束了。你可能会问为什么一定要先从j开始而不是先动i因为坑在左边你必须有东西来填这个坑。右边找到一个小的填过来左边才有资格腾出新的坑给右边的大元素。如果反过来先让i找大的你会面临一个尴尬局面左边坑还没填你又把一个大值挖走数组里就会同时出现两个坑逻辑就乱了。这个顺序不是约定俗成的摆设是保证单趟划分正确性的必要条件。2.2 一个完整的手推示例带你走一遍光说概念没用我拿一个具体数组手推一遍。假设数组是arr[6] {5, 3, 8, 2, 1, 7}区间是0到5第一个元素arr[0]5就是pivot。初始状态i0j5pivot5。arr[0]被挖走数组逻辑上变成[_ , 3, 8, 2, 1, 7]第一回合j从5开始往左找比5小的数j5arr[5]77不小于5继续。j4arr[4]11小于5停。把arr[4]1填到i0的坑里。数组变成[1 , 3, 8, 2, _, 7]现在坑在j4的位置。第二回合i从0开始往右找比5大的数i0arr[0]11不大于5继续。i1arr[1]33不大于5继续。i2arr[2]88大于5停。把arr[2]8填到j4的坑里。数组变成[1 , 3, _, 2, 8, 7]现在坑在i2的位置。第三回合j继续从4往左找比5小的数j4arr[4]88不小于5继续。j3arr[3]22小于5停。把arr[3]2填到i2的坑里。数组变成[1 , 3, 2, _, 8, 7]现在坑在j3的位置。第四回合i继续从2往右找比5大的数i2arr[2]22不大于5继续。i3此时i和j相遇了外层循环结束。最后把pivot5填到i3这个坑里。数组变成[1, 3, 2, 5, 8, 7]返回值是3。你可以检查一下5左边的1、3、2全都小于55右边的8、7全都大于5。这个位置就是5在有序数组中最终的归宿。如果你把整个过程在纸上画一遍你会明显感觉到“坑”像接力棒一样从左传到右又从右传回左最后停在中间。理解了这一次手推你就掌握了挖坑法的全部精髓。3. 完整实现与关键细节解析3.1 可以直接复制的C语言代码下面是一份完整的、自带测试用例的C语言实现。你在本地环境里编译运行可以立刻看到效果。#include stdio.h // 单趟划分以区间第一个元素为枢轴返回枢轴最终的下标 int partition(int arr[], int left, int right) { int pivot arr[left]; // 取出枢轴的值left位置变成“坑” int i left; int j right; while (i j) { // 从右向左找第一个小于pivot的元素填左边的坑 while (i j arr[j] pivot) { j--; } arr[i] arr[j]; // 从左向右找第一个大于pivot的元素填右边的坑 while (i j arr[i] pivot) { i; } arr[j] arr[i]; } // i和j相遇这个位置就是pivot的最终位置 arr[i] pivot; return i; } // 递归实现快速排序 void quickSort(int arr[], int left, int right) { if (left right) { return; } int pos partition(arr, left, right); quickSort(arr, left, pos - 1); // 排序左子区间 quickSort(arr, pos 1, right); // 排序右子区间 } void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {5, 3, 8, 2, 1, 7}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前: ); printArray(arr, n); quickSort(arr, 0, n - 1); printf(排序后: ); printArray(arr, n); return 0; }运行结果排序前: 5 3 8 2 1 7 排序后: 1 2 3 5 7 83.2 代码里那些一眼带过、暗藏杀机的细节这段代码看起来不长但我跟你说几乎每一行都有人在上面栽过跟头。第一个细节内层两个while循环的条件里为什么都必须带上i j你可以试想一下如果去掉内层的i jj可能会一直往左走到数组开头甚至更远i也可能一路冲到数组末尾之外。虽然pivot这个“哨兵”能挡住一部分越界情况但一旦数组里出现连续多个小于或大于pivot的元素指针就会悄悄跑飞轻则越界访问重则段错误。内层加i j不是冗余是保命符。第二个细节为什么内层比较时用的是和而不是和这涉及到等值元素怎么处理。如果去掉等号当arr[j]的pivot相等时循环会停下来然后发生交换而交换过去的元素和枢轴一样大下一轮又会被另一个指针停下如此往复指针卡死在原地外层while永远退不出去程序死循环。加上等号之后遇到相等的元素直接跳过等到i和j相遇为止既不会死循环也不会做无意义的交换。第三个细节递归终止条件写成left right而不是left right。有些情况下比如pivot恰好是区间最小值partition返回的pos等于left那么右区间是pos 1到right左区间是left到pos - 1也就是left到left - 1此时left大于right。如果不写这种空区间就会继续递归导致无限循环或者栈溢出。这个坑我见过太多人踩了。第四个细节partition返回的是i不是left也不是right。枢轴最终的位置是i和j相遇的地方它可能落在区间中间也可能落在边界上。返回正确的位置递归才能精确地切分左右区间。4. 第一个元素当枢轴最大的坑在哪里4.1 有序数组是怎么把快速排序拖垮的我先把结论放这里当输入数组已经有序时以第一个元素为枢轴的快速排序会退化成最坏时间复杂度O(n²)。为什么你想如果数组是{1, 2, 3, 4, 5, 6}第一个元素1是全局最小值。单趟划分结束后pivot被放回最左边左区间为空右区间是{2, 3, 4, 5, 6}。下一轮枢轴又是2依然是当前区间的最小值左区间依然为空右区间长度减一。就这样一刀一刀切下去每次只去掉一个元素递归深度变成了n总比较次数变成了n(n-1)/2和冒泡排序一个水平。如果你以为这种退化只在理论上存在那就天真了。实际开发中有序数据出现的频率远比想象中高数据库里按主键读出的记录、日志文件按时间排列的记录、接口返回的列表都是现成的有序或近似有序数据。如果你在排序这些数据时用了固定第一个元素当枢轴等于亲手埋下了一颗性能地雷。我自己做过一次很粗糙的实测10000个随机整数用这个实现排序耗时大概几毫秒换成10000个已经排好序的整数耗时直接飙升到几十毫秒甚至上百毫秒。数据量再大一点比如十万个有序数程序会明显卡顿递归深度过大甚至可能把栈空间耗尽直接栈溢出崩溃。这个反差比你想象中扎心得多。4.2 常用的补救手段以及和题目的关系既然问题出在“固定选第一个元素”那思路就是让枢轴的选取变得不那么死板。工程上常用的有三种手段。第一种是随机选枢轴。在区间内生成一个随机下标把这个位置的值和第一个元素交换然后继续用你熟悉的“以第一个元素为枢轴”的划分逻辑。这样即使数组本身有序每次枢轴落在区间中的位置也是随机的期望时间复杂度回到O(n log n)。我看到过有的同学不理解这种做法的合法性其实关键点在于快速排序的正确性只依赖“划分后左边都比枢轴小、右边都比枢轴大”枢轴到底选哪个元素无关紧要。随机交换只是改变了哪个值当枢轴并没有改变排序算法的骨架。第二种是三数取中。取区间左端、右端和中间位置三个值找出中间大小的那个把它换到第一个位置。这种做法避免了随机数生成的额外开销也不会碰运气碰到连续坏运气对付“近似有序”的数据效果显著。第三种是小区间插入排序。当递归划分的子区间长度小于某个阈值比如10到20时直接改用插入排序。插入排序在数据量小的时候常数极小而且没有递归开销能有效提升整体性能。很多工业级排序实现都会做这个优化。这里我多说一句题目要求“以第一个元素作为枢轴”你是不是觉得上面这些优化和题目冲突了不冲突。比如随机选枢轴或者三数取中你可以先做一次交换把新枢轴放到第一个位置接下来的划分逻辑依然是你熟悉的“第一个元素作为枢轴”。这相当于保留题目的划分框架只对“谁来当枢轴”做了一次预处理。你在练习时完全可以先实现基础版本再在这个版本上逐步加优化两条腿走路又稳又深。5. 调试历程与高频翻车点排行5.1 我当年调试时的真实经历第一次写这个算法的时候我犯过一个特蠢的错内层while的比较符号写反了。我写成了arr[j] pivot结果j一路往左猛冲把比枢轴大的元素全当“要找的目标”填到了左边一轮下来左边比右边还乱排序结果完全错误。当时我没有意识到是符号问题以为是递归边界写错了于是疯狂打印数组状态。打印了几轮之后我发现每次划分完之后枢轴左右两边并没有被正确切分才回头检查partition。你猜怎么着就这么一个和的问题我调了半个多小时。说这个故事是想告诉你遇到排序结果错乱别急着怀疑递归先检查单趟划分后的数组看看“左边比枢轴小、右边比枢轴大”这个铁律有没有被破坏。另一次更隐蔽。我在一个几乎全相等的数组上测试比如{3, 3, 3, 3, 3}程序倒是没死循环但跑得极慢递归栈一层接一层。后来才想明白全等数组其实也触发了最坏情况因为每个枢轴都落在区间一端每次划分只能去掉一个元素。这让我意识到性能退化不只有“有序”一种触发条件“大量重复元素”同样危险。5.2 高频问题速查表我把这些经验整理成一张表方便你排查问题。现象可能原因排查方法排序结果不对部分元素顺序混乱partition的比较符号写反或填坑顺序错误单步调试打印每趟划分后的数组检查“左边都小、右边都大”是否成立程序死循环卡住不动内层while缺少ij条件或等值元素处理不当检查内层两个while循环的条件确认带上了ij递归过深栈溢出崩溃输入数组有序或大量重复固定枢轴导致最坏情况改用三数取中或随机选枢轴必要时小区间用插入排序划分后枢轴位置不对返回的下标异常最后一步arr[i]pivot写错位置或返回的不是i而用了left/right用极小数组3到5个元素手推一遍与代码逻辑对照空区间无限递归终止条件写成leftright没考虑leftright的情况改成left right排查的时候我给你一个屡试不爽的建议测试用例从最小规模开始。先用两个元素的数组再用三个元素再用包含重复元素的小数组一步一打印。小用例能跑对再上大用例问题就能迅速定位。千万不要一上来就扔一个一万个随机数的数组进去黑盒测试会浪费你大量时间。6. 聊聊我自己的一点体会如果你把上面这些内容消化了你会发现自己不只是多背了一段代码而是把“以第一个元素作为枢轴”这个经典写法背后的原理、坑和优化方向都串起来了。以后再遇到别的排序算法或者面试官追问“为什么标准库排序不用固定枢轴”你都能接上话。我个人在实际动手中的体会是学这种经典算法最忌讳“代码能跑就万事大吉”。快速排序这种代码运行起来正确只是及格线真正见功夫的地方是你能不能在脑子里把单趟划分的每一步推演出来能不能说清楚等号为什么要加、边界为什么这样写、性能为什么退化。做到这一步你在面试时手写快排和那种背模板默写的状态完全是两个层次。最后再分享一个小技巧在测试这个算法时不妨故意准备三组数据一组随机、一组升序、一组全部相同分别观察它们的耗时和递归深度。当你亲眼看到有序数据把快速排序拖垮的那一刻你才算真正理解了“枢轴选择”这四个字的分量。这个经验比背一百遍理论都管用。 
长河君 · 2026/10/20 12:05:04 · 阅读 1.2k C语言快速排序：以第一个元素为枢轴的实现与避坑指南
先说一句掏心窝的话这道题我在课程作业、面试手写代码、甚至帮人改代码时都见过无数次。“C语言实现快速排序以第一个元素作为枢轴”听起来像教科书里最经典的开篇案例可真正动手写的时候大多数人卡在了同一个地方——单趟划分的指针移动顺序和边界条件。网上代码一搜一大把但能讲清楚为什么这么写、哪里容易翻车的真不多。这篇文章我不打算只丢一段能跑的代码给你。我会把“以第一个元素作为枢轴”这件事拆开揉碎从核心思路、单趟划分手推过程、完整C代码实现到最容易被忽略的性能退化问题再到我实际调试中踩过的坑一次性讲透。不管你是正在学数据结构的学生、准备算法面试的开发者还是想把这个经典写法真正吃透的C语言爱好者都能在这里找到你需要的东西。1. 这个题到底在考什么1.1 快速排序的核心思想一句话就能说清快速排序Quick Sort是典型的分治Divide and Conquer算法。它的核心思路其实特别朴素从待排序区间里挑一个元素把它当作“枢轴”pivot然后把剩下的元素分成两拨比枢轴小的放到它左边比枢轴大的放到它右边。这样一来枢轴元素就落在了它最终应该在的位置上。接下来就简单了枢轴左边的子区间和右边的子区间分别再做同样的事情递归下去。直到子区间里只剩一个元素或者空排序就结束了。这个过程有个特别直观的类比想象你是一群人的组织者你随机点名一个人当“标杆”然后让所有比他矮的人站到他左边所有比他高的人站到他右边。现在标杆的位置已经对了剩下要做的事情就是让左边那一堆人再重复这个动作右边那一堆人也重复这个动作。每一轮都在“归位”一个标杆递归下去所有人就都站好了。1.2 为什么题目偏偏指定“第一个元素当枢轴”“以第一个元素作为枢轴”这个要求很多人不理解觉得这不是很蠢吗如果数组本来就是有序的第一个元素当枢轴岂不是每次都把区间切成长度1和长度n-1这样极端不对称的两部分这里要分两层看。第一层教学和考试场景里这个指定是为了让算法的步骤“可预期”。不管你输入什么数组第一个元素是谁划分规则就是固定的这样老师可以手推步骤、出题考过程学生也容易验证自己写的代码对不对。它牺牲了一部分性能上的聪明劲儿换来了清晰和简单。第二层才是真正值得你记住的它暴露了“固定选枢轴”这一策略的天然缺陷。这种缺陷在工程上是致命的但在学习阶段却非常有价值——它逼你去思考为什么工业级的快速排序实现比如很多标准库里的排序函数都不会死板地用第一个元素当枢轴而是要加随机化或者三数取中。理解了这一点你才算真正把快速排序学透了而不只是背代码。我先说结论后面会专门用一整节来展开如果数组恰好是正序或逆序固定选第一个元素会导致快速排序退化成“慢速排序”时间复杂度从平均的O(n log n)直接掉到O(n²)。这不是危言耸听我实测过10000个有序整数排序耗时和10000个随机整数差了两个数量级。2. 单趟划分整个算法的灵魂2.1 挖坑法双指针的动态过程以第一个元素作为枢轴的实现方式里我个人最推荐的是“挖坑法”也叫挖坑填数法。原因很简单它把元素交换的动作变成了“挖坑”和“填坑”的交替移动对初学者来说极为直观也特别不容易在细节上出错。先把第一个元素的值用一个变量pivot保存起来。取出这个值之后在数组逻辑上就出现了一个“坑”它在最左边。接下来安排两个指针i指向左边界也就是坑的位置j指向右边界。规则就两条j从右往左走找到一个比pivot小的元素。找到了把它填到i当前的坑里。填完之后j的位置就变成了新的坑。i从左往右走找到一个比pivot大的元素。找到了把它填到j当前的坑里。填完之后i的位置又变成了新的坑。如此循环往复i和j互相往中间靠拢不停“填坑—产生新坑”。直到i和j相遇这个位置就是pivot的最终归宿把pivot填进去单趟划分就结束了。你可能会问为什么一定要先从j开始而不是先动i因为坑在左边你必须有东西来填这个坑。右边找到一个小的填过来左边才有资格腾出新的坑给右边的大元素。如果反过来先让i找大的你会面临一个尴尬局面左边坑还没填你又把一个大值挖走数组里就会同时出现两个坑逻辑就乱了。这个顺序不是约定俗成的摆设是保证单趟划分正确性的必要条件。2.2 一个完整的手推示例带你走一遍光说概念没用我拿一个具体数组手推一遍。假设数组是arr[6] {5, 3, 8, 2, 1, 7}区间是0到5第一个元素arr[0]5就是pivot。初始状态i0j5pivot5。arr[0]被挖走数组逻辑上变成[_ , 3, 8, 2, 1, 7]第一回合j从5开始往左找比5小的数j5arr[5]77不小于5继续。j4arr[4]11小于5停。把arr[4]1填到i0的坑里。数组变成[1 , 3, 8, 2, _, 7]现在坑在j4的位置。第二回合i从0开始往右找比5大的数i0arr[0]11不大于5继续。i1arr[1]33不大于5继续。i2arr[2]88大于5停。把arr[2]8填到j4的坑里。数组变成[1 , 3, _, 2, 8, 7]现在坑在i2的位置。第三回合j继续从4往左找比5小的数j4arr[4]88不小于5继续。j3arr[3]22小于5停。把arr[3]2填到i2的坑里。数组变成[1 , 3, 2, _, 8, 7]现在坑在j3的位置。第四回合i继续从2往右找比5大的数i2arr[2]22不大于5继续。i3此时i和j相遇了外层循环结束。最后把pivot5填到i3这个坑里。数组变成[1, 3, 2, 5, 8, 7]返回值是3。你可以检查一下5左边的1、3、2全都小于55右边的8、7全都大于5。这个位置就是5在有序数组中最终的归宿。如果你把整个过程在纸上画一遍你会明显感觉到“坑”像接力棒一样从左传到右又从右传回左最后停在中间。理解了这一次手推你就掌握了挖坑法的全部精髓。3. 完整实现与关键细节解析3.1 可以直接复制的C语言代码下面是一份完整的、自带测试用例的C语言实现。你在本地环境里编译运行可以立刻看到效果。#include stdio.h // 单趟划分以区间第一个元素为枢轴返回枢轴最终的下标 int partition(int arr[], int left, int right) { int pivot arr[left]; // 取出枢轴的值left位置变成“坑” int i left; int j right; while (i j) { // 从右向左找第一个小于pivot的元素填左边的坑 while (i j arr[j] pivot) { j--; } arr[i] arr[j]; // 从左向右找第一个大于pivot的元素填右边的坑 while (i j arr[i] pivot) { i; } arr[j] arr[i]; } // i和j相遇这个位置就是pivot的最终位置 arr[i] pivot; return i; } // 递归实现快速排序 void quickSort(int arr[], int left, int right) { if (left right) { return; } int pos partition(arr, left, right); quickSort(arr, left, pos - 1); // 排序左子区间 quickSort(arr, pos 1, right); // 排序右子区间 } void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {5, 3, 8, 2, 1, 7}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前: ); printArray(arr, n); quickSort(arr, 0, n - 1); printf(排序后: ); printArray(arr, n); return 0; }运行结果排序前: 5 3 8 2 1 7 排序后: 1 2 3 5 7 83.2 代码里那些一眼带过、暗藏杀机的细节这段代码看起来不长但我跟你说几乎每一行都有人在上面栽过跟头。第一个细节内层两个while循环的条件里为什么都必须带上i j你可以试想一下如果去掉内层的i jj可能会一直往左走到数组开头甚至更远i也可能一路冲到数组末尾之外。虽然pivot这个“哨兵”能挡住一部分越界情况但一旦数组里出现连续多个小于或大于pivot的元素指针就会悄悄跑飞轻则越界访问重则段错误。内层加i j不是冗余是保命符。第二个细节为什么内层比较时用的是和而不是和这涉及到等值元素怎么处理。如果去掉等号当arr[j]的pivot相等时循环会停下来然后发生交换而交换过去的元素和枢轴一样大下一轮又会被另一个指针停下如此往复指针卡死在原地外层while永远退不出去程序死循环。加上等号之后遇到相等的元素直接跳过等到i和j相遇为止既不会死循环也不会做无意义的交换。第三个细节递归终止条件写成left right而不是left right。有些情况下比如pivot恰好是区间最小值partition返回的pos等于left那么右区间是pos 1到right左区间是left到pos - 1也就是left到left - 1此时left大于right。如果不写这种空区间就会继续递归导致无限循环或者栈溢出。这个坑我见过太多人踩了。第四个细节partition返回的是i不是left也不是right。枢轴最终的位置是i和j相遇的地方它可能落在区间中间也可能落在边界上。返回正确的位置递归才能精确地切分左右区间。4. 第一个元素当枢轴最大的坑在哪里4.1 有序数组是怎么把快速排序拖垮的我先把结论放这里当输入数组已经有序时以第一个元素为枢轴的快速排序会退化成最坏时间复杂度O(n²)。为什么你想如果数组是{1, 2, 3, 4, 5, 6}第一个元素1是全局最小值。单趟划分结束后pivot被放回最左边左区间为空右区间是{2, 3, 4, 5, 6}。下一轮枢轴又是2依然是当前区间的最小值左区间依然为空右区间长度减一。就这样一刀一刀切下去每次只去掉一个元素递归深度变成了n总比较次数变成了n(n-1)/2和冒泡排序一个水平。如果你以为这种退化只在理论上存在那就天真了。实际开发中有序数据出现的频率远比想象中高数据库里按主键读出的记录、日志文件按时间排列的记录、接口返回的列表都是现成的有序或近似有序数据。如果你在排序这些数据时用了固定第一个元素当枢轴等于亲手埋下了一颗性能地雷。我自己做过一次很粗糙的实测10000个随机整数用这个实现排序耗时大概几毫秒换成10000个已经排好序的整数耗时直接飙升到几十毫秒甚至上百毫秒。数据量再大一点比如十万个有序数程序会明显卡顿递归深度过大甚至可能把栈空间耗尽直接栈溢出崩溃。这个反差比你想象中扎心得多。4.2 常用的补救手段以及和题目的关系既然问题出在“固定选第一个元素”那思路就是让枢轴的选取变得不那么死板。工程上常用的有三种手段。第一种是随机选枢轴。在区间内生成一个随机下标把这个位置的值和第一个元素交换然后继续用你熟悉的“以第一个元素为枢轴”的划分逻辑。这样即使数组本身有序每次枢轴落在区间中的位置也是随机的期望时间复杂度回到O(n log n)。我看到过有的同学不理解这种做法的合法性其实关键点在于快速排序的正确性只依赖“划分后左边都比枢轴小、右边都比枢轴大”枢轴到底选哪个元素无关紧要。随机交换只是改变了哪个值当枢轴并没有改变排序算法的骨架。第二种是三数取中。取区间左端、右端和中间位置三个值找出中间大小的那个把它换到第一个位置。这种做法避免了随机数生成的额外开销也不会碰运气碰到连续坏运气对付“近似有序”的数据效果显著。第三种是小区间插入排序。当递归划分的子区间长度小于某个阈值比如10到20时直接改用插入排序。插入排序在数据量小的时候常数极小而且没有递归开销能有效提升整体性能。很多工业级排序实现都会做这个优化。这里我多说一句题目要求“以第一个元素作为枢轴”你是不是觉得上面这些优化和题目冲突了不冲突。比如随机选枢轴或者三数取中你可以先做一次交换把新枢轴放到第一个位置接下来的划分逻辑依然是你熟悉的“第一个元素作为枢轴”。这相当于保留题目的划分框架只对“谁来当枢轴”做了一次预处理。你在练习时完全可以先实现基础版本再在这个版本上逐步加优化两条腿走路又稳又深。5. 调试历程与高频翻车点排行5.1 我当年调试时的真实经历第一次写这个算法的时候我犯过一个特蠢的错内层while的比较符号写反了。我写成了arr[j] pivot结果j一路往左猛冲把比枢轴大的元素全当“要找的目标”填到了左边一轮下来左边比右边还乱排序结果完全错误。当时我没有意识到是符号问题以为是递归边界写错了于是疯狂打印数组状态。打印了几轮之后我发现每次划分完之后枢轴左右两边并没有被正确切分才回头检查partition。你猜怎么着就这么一个和的问题我调了半个多小时。说这个故事是想告诉你遇到排序结果错乱别急着怀疑递归先检查单趟划分后的数组看看“左边比枢轴小、右边比枢轴大”这个铁律有没有被破坏。另一次更隐蔽。我在一个几乎全相等的数组上测试比如{3, 3, 3, 3, 3}程序倒是没死循环但跑得极慢递归栈一层接一层。后来才想明白全等数组其实也触发了最坏情况因为每个枢轴都落在区间一端每次划分只能去掉一个元素。这让我意识到性能退化不只有“有序”一种触发条件“大量重复元素”同样危险。5.2 高频问题速查表我把这些经验整理成一张表方便你排查问题。现象可能原因排查方法排序结果不对部分元素顺序混乱partition的比较符号写反或填坑顺序错误单步调试打印每趟划分后的数组检查“左边都小、右边都大”是否成立程序死循环卡住不动内层while缺少ij条件或等值元素处理不当检查内层两个while循环的条件确认带上了ij递归过深栈溢出崩溃输入数组有序或大量重复固定枢轴导致最坏情况改用三数取中或随机选枢轴必要时小区间用插入排序划分后枢轴位置不对返回的下标异常最后一步arr[i]pivot写错位置或返回的不是i而用了left/right用极小数组3到5个元素手推一遍与代码逻辑对照空区间无限递归终止条件写成leftright没考虑leftright的情况改成left right排查的时候我给你一个屡试不爽的建议测试用例从最小规模开始。先用两个元素的数组再用三个元素再用包含重复元素的小数组一步一打印。小用例能跑对再上大用例问题就能迅速定位。千万不要一上来就扔一个一万个随机数的数组进去黑盒测试会浪费你大量时间。6. 聊聊我自己的一点体会如果你把上面这些内容消化了你会发现自己不只是多背了一段代码而是把“以第一个元素作为枢轴”这个经典写法背后的原理、坑和优化方向都串起来了。以后再遇到别的排序算法或者面试官追问“为什么标准库排序不用固定枢轴”你都能接上话。我个人在实际动手中的体会是学这种经典算法最忌讳“代码能跑就万事大吉”。快速排序这种代码运行起来正确只是及格线真正见功夫的地方是你能不能在脑子里把单趟划分的每一步推演出来能不能说清楚等号为什么要加、边界为什么这样写、性能为什么退化。做到这一步你在面试时手写快排和那种背模板默写的状态完全是两个层次。最后再分享一个小技巧在测试这个算法时不妨故意准备三组数据一组随机、一组升序、一组全部相同分别观察它们的耗时和递归深度。当你亲眼看到有序数据把快速排序拖垮的那一刻你才算真正理解了“枢轴选择”这四个字的分量。这个经验比背一百遍理论都管用。