企业官网建设流程全解析

【数据结构】快速排序专题

🔥 H.莓飛： 个人主页

❄️个人专栏：「C++」「数据结构」「Linux系统编程」

✨ 心不畏死，踏屍前行。

📦 代码仓库：cocatrice_csdn_code

📖 博主简介：

概览

• 快排的递归骨架与前序遍历同形
• hoare 版本：左右指针往中间走
• 挖坑法：把 key 抠走留一个坑
• 前后指针法：prev 与 cur 一路往右
• 三种划分在同一组数据上的落点
• key 取最左边还是三数取中
• 小区间换插入排序
• 递归改非递归，栈里存左右端点
• 内省排序：深度超限换堆排序
• 快排的时间、空间与递归栈深

核心知识

一、快排的骨架

快速排序要做的事可以拆成两个动作：先在这个区间里挑一个基准值，把比它小的挪到左边、比它大的挪到右边，让基准值落到最终位置上；再对基准值左右这两段各做一遍同样的事。基准值归位那一步叫划分，左右两段的那一步叫递归，两件事凑起来就是这个算法的全部。

把递归树画出来，形状跟之前讲二叉树时画的前序很像：根节点是第一次划分，先干活再往左右两边分，左子树走完才轮到右子树，这是典型的前序遍历。区别在于二叉树的左右子树是链表挂上去的，快排的左右两段是同一块数组里的两个下标区间，它们共用一块内存，不需要任何额外节点。

图 1 快排的递归骨架：先处理自己，再处理左右两段

递归的出口是区间为空或者只剩一个元素。写成代码就是进入函数之后先看 left 和 right 的关系，left 大于等于 right 直接返回，因为长度为零或者一的一段本来就排好了。这一步很容易被漏掉，漏掉之后递归永远收不回来，程序会一直往更小的区间分下去直到栈溢出。

划分一次要把整个区间扫一遍，代价是这一段的长度；递归树每往下一层，所有区间加起来的总长度还是原来那个数。于是总耗时可以写成一个递推式：长度为 N 的一趟，代价是 N；下一层是两个大约 N 除以 2 的区间，代价加起来还是 N；层数决定了乘几次。分层均匀的时候层数是 log N，总代价就是 N log N，这就是快排平均复杂度的来由。

二、hoare 版本

最早的那版划分只用两个游标，一个从左往右找比基准值大的，一个从右往左找比基准值小的，两边各找到一个就交换，直到两个游标相遇，最后把基准值换到相遇点上。

intPartHoare(int*a,intleft,intright){intkeyi=left;while(left<right){while(left<right&&a[right]>=a[keyi]){right--;}while(left<right&&a[left]<=a[keyi]){left++;}Swap(&a[left],&a[right]);}Swap(&a[keyi],&a[left]);returnleft;}

图 2 i 往右找比 key 大的，j 往左找比 key 小的，找到就换

这段代码有三个地方值得注意，其中一个是内存越界。内层的两个 while 里都带着 left 小于 right 这个条件，它保证了游标不会冲出区间：右侧游标一路往左扫的时候，就算整段都比基准值大，它也会在碰到左侧游标的位置停下来；左侧游标同理。少了这个条件，极端数据上就会读到数组外面去。

第二个地方是先让右边走，这一步不能反，原因落在相遇点的取值上：右侧游标停下来的时候，它脚下那个值一定不大于基准值，左侧游标停下来的时候，它脚下那个值一定不小于基准值。先走右边，相遇点就会落在右侧游标停下的位置上，那个位置的值不大于基准值，把它跟最左边的基准值交换之后，基准值左边全是小的、右边全是大的，划分才成立。要是先走左边，相遇点可能落在一个比基准值大的位置上，交换完基准值右边还藏着小的元素，递归下去这段永远排不对。

第三个地方是两个比较都用带等号的写法。用大于等于和小于等于，等于基准值的元素会被两边一起跳过，不会卡在游标脚下形成死循环。代价是重复元素会被分到同一侧，这一点在后面讲重复数据的时候会成为性能问题。

拿第一组数据 6 1 7 6 6 6 4 9 走一遍。基准值是第一个 6，右侧游标从 9 开始往左扫，9 和最后一个 6 都不小于 6，一直扫到 4 停下；左侧游标从最左边出发，6 和 1 都不大于 6，扫到 7 停下。两个游标一交换，数组变成 6 1 4 6 6 6 7 9，接着右侧游标继续左移，一路都是 6，最后跟左侧游标在第 2 位相遇。把基准值换过去，数组是 4 1 6 6 6 6 7 9，返回的落点是 2。

三、挖坑法

挖坑法换个角度描述同一件事：把基准值从最左边抠出来单独存着，那个位置就空成了坑；从右边找一个比基准值小的，填进坑里，它原来的位置又变成新坑；再从左边找一个比基准值大的，填进这个新坑。坑在左右之间来回跳，跳到最后两个游标相遇，把单独存着的那个基准值放进最后这个坑里。

intPartHole(int*a,intleft,intright){intkey=a[left];inthole=left;while(left<right){while(left<right&&a[right]>=key){right--;}a[hole]=a[right];hole=right;while(left<right&&a[left]<=key){left++;}a[hole]=a[left];hole=left;}a[hole]=key;returnhole;}

图 3 先把 key 拿走，空出一个坑，再从右边找个小的填进来

跟 hoare 版本比，这里少了一次交换。hoare 每次要交换两个位置的值，一次交换是三趟赋值；填坑只需要把值写进坑里，一趟赋值就够。省下的那点开销在大数组上能看出来，不过也没有想象中大，因为划分的耗时主要花在游标扫描和内存访问上，赋值本身只占一小部分。

在这台机器上用一百万条随机数据跑，hoare 版本 80.280 毫秒，挖坑版本 82.939 毫秒，挖坑反而慢了一点。这个结果看上去违背了刚说的道理，其实是编译器把交换那一对赋值优化掉了，两边生成的机器码差不多，剩下的差别落在循环结构和分支预测上，属于测量噪声的量级。

挖坑法的好处在理解成本上：坑这个概念一画出来，每一步在做什么就很直白，画图讲解和写代码能对得上，面试里被要求手写划分的时候，这一版最不容易写错。

四、前后指针法

前后指针法只用两个往右走的游标，prev 停在「已经确认比基准值小的那一段的最后一个位置」，cur 在前面一路找比基准值小的值，找到一个就把 prev 往前挪一格，跟 cur 换一下，把小值收进那段里。

intPartPrevCur(int*a,intleft,intright){intkeyi=left;intprev=left;intcur=left+1;while(cur<=right){if(a[cur]<a[keyi]&&++prev!=cur){Swap(&a[prev],&a[cur]);}cur++;}Swap(&a[keyi],&a[prev]);returnprev;}

图 4 prev 守着小于 key 的最后一位，cur 一路往前找小的

那个 ++prev 跟判断写在一个条件里，是这一版最容易读错的地方。它的意思是：先看 cur 脚下这个值是不是比基准值小，是的话就把 prev 挪到下一个位置，再看 prev 和 cur 是不是同一个位置，同一个位置不用换，不是同一个位置才交换。把 ++prev 写在条件外面也能跑对，但会多算一次自增，写在一起的版本在循环体内只留一个判断。

前后指针法跟 hoare 版本落点不总相同，这一点拿数据一看就清楚。还是第二组 3 2 3 3 3 3 2 3，hoare 版本最后落在第 6 位，前后指针法落在第 2 位，两种划分给出的两段长度差了三倍。落点不同不影响最终结果，但会直接影响递归树的形状，也就直接影响耗时。

百万条随机数据上这一版 80.141 毫秒，跟 hoare 的 80.280 毫秒基本打平。它的优势落在结构上：一趟单向扫描，没有左右相向的双指针，改成三路划分的时候只需要在循环里多接一个分支，这一点在后面第五节和第十一节会再碰面。

五、三种划分的对比

同一组数据走三种划分，落点差别可以直接列成表。下面三组数据都只有八个元素，跑完之后打印整个数组和落点：hoare 与前后指针法各返回一个位置，三路划分返回的是一段等于区间的左右端点。

图 5 同一组数据 6 1 7 6 6 6 4 9 在三种划分下的落点

第一组数据三个落点里有两点一致：hoare 和前后指针都把基准值放在第 2 位，划分完的数组都是 4 1 6 6 6 6 7 9，左边两个、右边五个。三路划分的结果是 1 4 6 6 6 6 9 7，等于段从第 2 位到第 5 位，四个 6 一次性归位，递归只需要处理左边的一个 1 和右边的一个 9 与 7。这组数据上三种划分都能接受，三路划分还更快一点，因为它把四个 6 整段跳过了。

第二组数据的落点差距最大，hoare 落在第 6 位，也就是说划分完左边留下六个元素、右边只剩一个，下一层递归要处理一个长度 6 的区间；前后指针法落在第 2 位，左边两个、右边五个。三路划分把第 2 位到第 7 位的六个 3 整段拿下，剩下的只有左边两个 2。数组里重复值扎堆的时候，前两种划分给出的两段长度完全取决于游标怎么扫，跟「均匀切一半」的直觉差得很远。

第三组八个 2 是极端情况，hoare 和前后指针法都落在第 0 位，意思是划分完基准值还在最左边，右边还是整整七个元素，下一层递归只比上一层少了一个元素；三路划分把第 0 位到第 7 位整段归位，一次递归就结束。同一组数据，前两种写法要递归七层，三路划分一层就完事，这就是第十节要展开讲的那件事。

百万条随机数据上四种写法的耗时排在一起，差距小得可以忽略：

随机数据里重复值少，三种划分给出的两段长度都接近一半，递归树的形状差不多，所以耗时拉不开。三路划分反而慢了 8.6%，原因是每处理一个元素都要多做一次比较，区分它是小于、等于还是大于基准值，这份开销在随机数据上收不回来。划分写法的选择不看随机数据，看的是数据里重复值和有序程度有多重。

六、key 怎么选

基准值取哪个位置，决定了划分之后两段有多长。最直接的取法是最左边那个元素，代码里一行就够；代价是遇到已经有序的数据时，每次划分都会把最小的值放到最左边，两段长度变成 0 和 n 减 1，递归树退化成一条链，深度变成了 n。

把这条链的代价量出来并不难：让 hoare 版本跑已经升序排好的数据，两万条耗时 88.707 毫秒，四万条耗时 357.638 毫秒，数据翻一倍、耗时翻了 4.03 倍，这是标准的平方增长。照这个速度推下去，一百万条要跑好几个小时，实际根本跑不完。

三数取中的办法是把左端、中间、右端三个位置的值取出来，选大小排在中间的那个当基准值，再把它换到最左边去，后面的划分代码一行都不用改。

staticintMidOfThree(int*a,intleft,intright){intmid=left+(right-left)/2;if(a[left]<a[mid]){if(a[mid]<a[right]){returnmid;}returna[left]<a[right]?right:left;}if(a[left]<a[right]){returnleft;}returna[mid]<a[right]?right:mid;}

图 6 左中右三个值取中间那个，当 key 最不容易踩到最值

这段代码没有循环，全是比较和三元表达式，看上去绕，逻辑其实很直白：左端小于中间值的时候，中间值再小于右端，中间值就是中位数；中间值不小于右端的情况下，再看左端跟右端谁大，大的那个是中位数。左端不小于中间值的时候反过来处理一遍。写完拿几组数据手推一次就能确认，比如左中右分别是 9、7、8，中位数是 8。

换成三数取中再跑同一份升序数据，一百万条只要 11.798 毫秒，跑完校验有序。从「跑不完」到 11.798 毫秒，中间没有换算法，只是把基准值的取法从固定的最左边改成了看三处再决定。

随机取基准值是另一种常见做法：在区间里随机抽一个位置，跟最左边换一下，再走原来的划分。它在理论上能打散任何刻意构造的数据，包括那些专门针对三数取中设计的数据，代价是每次划分都要调一次随机数发生器。伪随机数在 C 语言里是几次乘加，摊到每次划分上不算贵，但在小数组上占比会明显起来。

这两种取法在工程里各有用处：数据由自己生成、长度又比较大的场合，三数取中就能应付过去，而且没有随机数带来的不确定性；数据来路不明，或者要防着别人构造最坏输入，加一层随机更稳妥。这两种也可以叠加，先随机抽三个位置再取中位数，代价是多几次内存访问。

七、小区间换成插入排序

递归往下分到区间很短的时候，快排的划分就不再是好的选择。长度为 8 的区间，划分一次要做八九次比较加若干次交换，然后再递归两次，每次进函数都要压栈、判空、算下标；而同样长度的区间用插入排序处理，比较次数差不多，但全是顺序访问，没有函数调用的开销。

常见的做法是设一个阈值，区间长度不超过它就不再往下分，直接调插入排序把这一小段排好。这个阈值取多少，跟机器、编译器、数据类型都有关系，我在这台机器上用一百万条随机数据扫了一遍，从 1 一直扫到 2048：

表里的形状很有意思：阈值从 1 涨到 64，耗时一路往下降，64 处最低；过了 64 又开始往上涨，到 2048 已经比不换插入还慢了将近三倍。前半段下降是因为省下的递归与划分开销比插入排序多出来的比较更值钱；后半段上涨是因为插入排序的平方项开始接管，一段长度 2048 的区间内部要比较两百万次左右，比快排分下去还贵。

我这套代码里写的是 16，它比最优的 64 慢 5.7%，两者之间的差别在大数组上只值几毫秒。工程代码里常见的取值落在 8 到 32 之间，原因不在这个区间最快，在于它在各种数据形态上都稳：随机数据上差别不大，接近有序的数据上小阈值能让更多段落到插入排序手里，那段数据本来就近乎有序，插入排序几乎不用搬东西。

阈值还有一个隐含的好处是压低递归深度。每多分一层就要多压一层栈帧，阈值把小段截住之后，递归树的高度大约等于 log2(N 除以阈值)，长度一百万、阈值 16 的时候只有 16 层，栈的开销可以忽略。

八、递归改非递归

把快排写成非递归，关键是想清楚递归版里那些「还没处理的任务」到底是什么。递归进左段之前，右段的左右端点还等着被处理，它们存在函数的栈帧里；换成手写的栈，就是把这些端点对存进一个自己管理的数组。

图 7 递归改成用栈，栈里存的就是左右端点这一对

voidQuickSortNonR(int*a,intn){if(n<2){return;}Range*st=(Range*)malloc(sizeof(Range)*(size_t)n*2);inttop=0;st[top].left=0;st[top].right=n-1;top++;while(top>0){top--;intleft=st[top].left;intright=st[top].right;if(left>=right){continue;}intkeyi=PartHole(a,left,right);if(keyi-1>left){st[top].left=left;st[top].right=keyi-1;top++;}if(keyi+1<right){st[top].left=keyi+1;st[top].right=right;top++;}}free(st);}

栈的容量开成两倍 n，是为了保证任何划分结果都不会溢出。这个上限是按最坏情况推出来的：每次划分把区间切成长度 1 和长度 n 减 1，两个子区间里只有一个需要压栈，另一个长度为零直接被 if 挡掉，所以栈里同时存在的区间数不会超过 n 个；两个都压进去的时候，压进去的两段加起来比上一段少一个元素，同样的道理让同时存在的区间数不超过 n。两倍是留的余量，实际用到的远小于这个数。

这段代码里两个 if 是提前筛掉空区间，省得把长度为零或者一的区间也压进栈里再弹出来检查一遍。非要省掉这两个 if 也能跑对，因为弹出来之后第一件事就是判断 left 是否大于等于 right，只不过多了一轮压栈弹栈。

百万条随机数据上，非递归版 79.285 毫秒，递归版 87.122 毫秒。这两个数字不能直接理解成「非递归更快」，因为两份代码用的划分不一样：非递归那一版用的是挖坑法，递归那一版用的是三路划分。第四节已经量过，百万条随机数据上挖坑 82.939 毫秒、三路 87.173 毫秒，两者本来就差这么多。递归与非递归真正的差别在调用开销上，在这个规模上被划分的耗时盖住了，量不出明显区别。

非递归版真正的价值在栈溢出上：递归深度按理论是 log2 n，长度一百万大概 20 层，看起来不用担心；但数据被打成最坏形状的时候深度会变成 n，栈帧一层几十字节，十万层就能把默认栈打穿。手写的栈放在堆上，最坏情况也只是多占几 MB 内存，程序不会崩。

九、退化的根源

快排的平均复杂度是 N log N，最坏复杂度是 N 的平方，两者之间的分水岭只有一件事：每次划分之后，基准值左右两段里最长的那一段有多长。两段长度接近，递归树就是一棵矮胖的树，层数 log N；两段长度差得远，树就细高，层数逼近 N。

看第二组数据 3 2 3 3 3 3 2 3 在 hoare 版本下的划分结果就更清楚：基准值是第一个 3，划分完落在第 6 位，左边六个、右边一个。下一层要处理长度 6 的区间，比上一层的 8 只少了 2 个元素，递归树差不多是一根斜线。八个 2 那组更极端，落点 0，每层只减少一个元素，深度就是 8。

把这条斜线换成比较次数：长度为 n 时第一次划分比较 n 次，第二次划分比较 n 减 1 次，一直到 1 次，加起来是 n 乘 n 除以 2。n 等于一百万时这个数字是五千万万，比平均情况的 2000 万次多出好几个数量级，机器跑不动就是这么来的。

退化有两条来路，要分开看：一条是数据本身有序或者逆序，基准值取最左边，遇到升序数组每次都取到最小值，两段变成空和 n 减 1，这一种靠改基准值的取法就能解决，第六节的三数取中就是干这个的。另一条是数据里有大量与基准值相等的元素，不管基准值取在哪，只要划分只分出「小于等于」和「大于等于」两段，等于基准值的那些元素就会全部堆到一边，递归还得一个个比过去，这一种改基准值的取法没用，得换划分写法，也就是下面两节要讲的内容。

分辨这两条来路的办法很直接：跑一遍基准值取最左边的版本，如果数据有序才慢，那是第一种；如果数据里重复值多，改成三数取中之后仍然慢，那是第二种。两种都中招的情况也有，那就得同时上三数取中和三路划分。

十、大量重复数据

把十万条全是 7 的数据喂给三种划分，结果差得离谱：hoare 版本 3008.276 毫秒，前后指针法 2992.172 毫秒，三路划分 0.088 毫秒，内省排序也是 0.088 毫秒。前两者比后者慢了三万四千倍，而数据本身只有十万条。

慢的原因在第二节埋的伏笔里：内层两个比较用的是大于等于和小于等于，一整段全是 7 的时候，右侧游标第一步就被 7 挡不住、一路退到最左边，左侧游标也一步不退，相遇点就是最左边的位置，返回落点 0。下一层递归要处理右边长度 99999 的区间，再下一层 99998，一路减下去，比较次数是十万乘十万除以二除以二，三千毫秒的量级就是这么来的。

前后指针法同样分不开，它的判断条件是当前值严格小于基准值，全 7 的数据里这个条件一次都不成立，prev 从头到尾停在最左边，最后把基准值跟 prev 交换，等于原地没动，落点还是 0，两种情况下的递归都在原地打转。

三路划分之所以是 0.088 毫秒，是因为它在第一层就把「等于基准值」的整段区间标出来了：十万个 7 全部落在等于段里，等于段是下标 0 到 99999，左右两段都是空的，递归一层都不往下走。三千毫秒变成零点零几毫秒，差别不在常数上，在算法结构上。

这里也能看出「两段划分」这个说法的局限。hoare 版本的划分只回答「这个元素该在基准值左边还是右边」；遇到等于基准值的元素，它被迫选一边放，等于段就被拆散了，下一层递归还得重新比一遍。三路划分回答的问题更细：小于、等于、大于各归各的位置，等于段一次归位，后面再也不碰。

十一、三路划分

三路划分把一个区间分成三段：小于基准值的、等于基准值的、大于基准值的。划分结束之后，等于段里每个元素都在自己的最终位置上，递归只需要处理左边那段和右边那段，中间整段不用再碰。

voidPart3Way(int*a,intleft,intright,int*leftKeyi,int*rightKeyi){intkey=a[left];intlt=left;intgt=right;intcur=left+1;while(cur<=gt){if(a[cur]<key){Swap(&a[lt],&a[cur]);lt++;cur++;}elseif(a[cur]>key){Swap(&a[cur],&a[gt]);gt--;}else{cur++;}}*leftKeyi=lt;*rightKeyi=gt;}

三个下标的含义要先定清楚，代码才好读：区间被切成三段，左边从 left 到 lt 减 1 是已确认小于基准值的部分，右边从 gt 加 1 到 right 是已确认大于基准值的部分，中间从 lt 到 cur 减 1 是已确认等于基准值的部分，cur 到 gt 是还没看过的部分。

每轮循环看 cur 脚下这个值，它比基准值小就换到左边去，把 lt 往前推一格，cur 也往前走一格；它比基准值大就换到右边去，gt 往回收一格，注意这时候 cur 不能动，因为换过来的那个值还没看过；它等于基准值就 cur 往前走，把它留在中间那段。循环结束的时候 lt 到 gt 就是等于段。

拿第一组数据 6 1 7 6 6 6 4 9 走一遍，基准值是第一个 6。cur 从第 1 位开始，1 比 6 小，换到左边去，lt 挪到 1；第 2 位的 7 比 6 大，换到最右边，gt 收到 6；接着依次看下去，中间遇到的 6 都留在原地，4 被换到左边，9 被换到右边。跑完数组是 1 4 6 6 6 6 9 7，等于段是第 2 位到第 5 位，四个 6 全部归位，递归只剩左边的 1 和右边的 9 与 7 两小段。

第二组 3 2 3 3 3 3 2 3 跑完是 2 2 3 3 3 3 3 3，等于段从第 2 位到第 7 位，六个 3 一次归位。第三组八个 2 跑完等于段是第 0 位到第 7 位，整个区间归位，递归直接结束。这三个结果就是第五节那张表里第三列的数字。

递归部分的写法跟之前不同，要把两段的端点都接住：拿回 leftKeyi 和 rightKeyi 之后，左边递归 left 到 leftKeyi 减 1，右边递归 rightKeyi 加 1 到 right。等于段中间的写法容易写错，写成 leftKeyi 加 1 到 rightKeyi 减 1 也能跑，只是白白多递归一层，那一层里全是相等的值，划分完什么都没变。

代价也是明摆着的：每个元素要跟基准值比两次，一次判小于、一次判大于，随机数据上比两段划分多出一次比较的开销。第五节那张表里三路划分 87.173 毫秒比 hoare 的 80.280 毫秒慢 8.6%，说的就是这份开销。数据里重复值占的比例上去之后，这份开销会被省下的递归抵消掉，到全等值的时候差距变成三万四千倍。

十二、内省排序

三路划分能解决重复值，解决不了「数据被打成最坏形状」这件事。前面第六节说过，三数取中能挡住已经有序的数据，但挡不住刻意构造的数据；而这种输入在真实场景里并不少见，比如很多日志按时间戳追加，而快排的基准值取法又刚好撞上那个分布。内省排序的思路是加一道保险：不指望快排在所有数据上都表现好，一旦发现递归深度不对劲，就换成最坏情况有保证的堆排序。

图 8 内省排序：一段区间进来，三条出口

staticvoidIntroRecurse(int*a,intleft,intright,longdepth,longlimit){if(left>=right){return;}if(right-left+1<=g_threshold){InsertSortRange(a,left,right);return;}if(depth>limit){g_switchCount++;HeapSortRange(a,left,right);return;}intlk=0,rk=0;Part3Way(a,left,right,&lk,&rk);g_depthNow++;if(g_depthNow>g_depthMax){g_depthMax=g_depthNow;}IntroRecurse(a,left,lk-1,depth+1,limit);IntroRecurse(a,rk+1,right,depth+1,limit);g_depthNow--;}

三个出口按顺序判断：区间为空或者只剩一个元素，直接返回；区间长度不超过阈值，交给插入排序；递归深度超过上限，整段交给堆排序。三条都没命中，才走三路划分继续往下分。

深度上限取成两倍的 log2 n，写成代码就是把 n 一路右移数位数：

staticlongDepthLimit(intn){longd=0;while(n>1){n>>=1;d++;}returnd*2;}

长度十万时，log2 十万取整是 16，上限就是 32 层。理想情况下递归树的高度是 17 层左右，所以这个上限留了一倍余量，正常数据永远碰不到；真碰上了，说明划分一直不均衡，继续分下去就是往平方复杂度上撞。

拿已经升序排好、而且基准值固定取最左边的数据来试，这是最容易把快排打穿的一类输入。十万条跑完只要 8.162 毫秒，最大递归深度 32，第一次换堆排序就发生在第 32 层，一共换了 6 段，最后结果有序。要是没有这道保险，同样十万条升序数据按第六节的增长速度推下去，要跑几十秒。

随机数据上这道保险也不碍事：十万条随机值跑 7.039 毫秒，qsort 11.100 毫秒，最大深度 32，一共触发了 9 次换路。深度能贴到上限，说明三路划分在随机数据上也有个别段落分得不够匀，这正是兜底应有的作用：那 9 段的收尾交给堆排序，代价是常数级的，换成快排继续硬分才可能出问题。

堆排序那部分的实现要点是就地做，不申请新数组。它把区间当成一棵完全二叉树，先把整段调成大顶堆，再把堆顶跟末尾交换、长度减一、重新向下调整，反复到只剩一个元素为止。这里用到的两个函数是之前写堆那篇里的同一份代码，换了个区间起点而已。

十三、排序数组那道题为什么卡 hoare

LeetCode 912 题要求把一个整数数组升序排好，接口只给数组和长度，不允许调用库里的排序。这道题看上去像是在考「你会不会写快排」，实际上它的测试数据里塞了大量重复值，专门用来卡只会写两段划分的解法。

在本机复现一遍这个场景：造十万条全是 7 的数据，分别喂给第二节和第十一节的写法。hoare 版本 3008.276 毫秒，前后指针法 2992.172 毫秒，这个量级在评测机上已经超时；三路划分 0.088 毫秒，内省排序也是 0.088 毫秒。同一份数据、同一台机器，差的只是划分写法。

数据里重复值多的时候，两段划分的落点会挤到区间的一端，递归树退化成一根斜线，复杂度从 N log N 掉到 N 的平方。第十节把这件事拆开讲过，结论落在落点 0 上：十万条数据要递归十万层，每层扫一遍剩下的元素，总比较次数是十万乘十万除以二。

这道题的正确解法有三个方向：第一个是换三路划分，等于段整段跳过，重复值越多越占便宜，全等值的时候一层就结束。第二个是内省排序，深度超限换堆排序，最坏情况被压到 N log N。第三个是用归并排序或者堆排序，两者都是稳定的 N log N，代价是归并要一块额外数组、堆排序常数大一点。

这里也提醒一件事：很多题解在 912 上贴的 hoare 版本是能过的，区别往往在比较符号上。用严格大于和严格小于，遇到等于基准值的元素就交换，重复值会被打散到两侧，落点更接近中间，反而不会退化；用带等号的写法才是我这里量到的 3008 毫秒。两种写法都不算错，但它们的失败条件完全不同，写的时候心里要清楚自己选的是哪一种。

十四、快排的时间、空间与递归栈深

把前面十三节的内容收拢成几条结论，下面按时间、空间、稳定性分开说。

时间复杂度分三种情况，平均是 O(N log N)，前提是每次划分把区间切成两段差不多长的；最好也是 O(N log N)，划分恰好对半分的时候递归树最矮；最坏是 O(N 的平方)，划分每次都切出长度 0 和 n 减 1，重复值扎堆和基准值固定取最左边是两种典型触发条件。

空间复杂度要看递归栈，平均情况下递归深度是 O(log N)，实测十万条随机数据最大深度 32 层，跟理论上的两倍 log2 N 吻合；最坏情况深度是 O(N)，十万条全等值数据用两段划分就是这个形状，三千毫秒里有相当一部分花在压栈弹栈上。除了栈之外，快排不需要额外数组，划分是就地完成的，这也是它比归并排序省内存的地方。

递归改成非递归之后，空间从栈挪到了堆上。第八节那份代码按最坏情况开了两倍 n 个区间对，十万条就是 160 万字节，长度一千万时要开 160 MB，这就不能算省内存了；实际可以按理论深度开一个更小的栈，比如 64 层，快满了就报错或者退回堆排序，工程代码里常见的做法是只开 log2 n 加一个余量那么大。

稳定性这一项，快排是不稳定排序，举一组最小的反例就够：三个记录分别是 3a、3b、1，hoare 版本以第一个 3 为基准值，右侧游标在 1 处停下，左侧游标一路走到跟它相遇的第 2 位，把基准值 3a 换到第 2 位，结果变成 1、3b、3a。两个关键字相等的记录 3a 和 3b 的先后次序被调换了，所以它不稳定。

需要稳定排序的场合得换算法，归并排序和计数排序都是稳定的，这一点在讲归并的那篇里会展开。快排之所以仍然是最常用的通用排序，是因为它的常数小、就地排序、缓存友好，稳定性在大多数场景里并不是硬要求。

一张表把四种写法的取舍收在一起：

踩坑点

• 划分里先让左边走，hoare版本必须先移动右侧游标，否则相遇点可能取到一个比基准值大的元素，交换之后基准值右边混进小元素，递归下去那段永远排不对，而且这种错误在多数随机数据上看不出来，只在特定分布上暴露。
• 内层 while 漏掉边界判断。右侧游标的比较条件在整段都比基准值大的时候会让 right一路减到负一，读到数组外面的内存。两个游标的条件里都要写上 left 小于 right，少一个都可能越界。
• 把划分的返回值用错地方，hoare与前后指针法返回的是基准值最终落下的位置，可以直接用它分左右两段；三路划分返回的是整段的左右端点，递归要跳到 leftKeyi 减 1 和 rightKeyi 加 1，写成 leftKeyi 和 rightKeyi 就会把等于段又递归一遍。
• 小区间阈值设得太大，第七节的数据显示阈值 2048 时百万条要 251.016 毫秒，比不换插入的 88.107毫秒慢将近三倍，原因是每个 2048 长的块内部要做两百万次比较。阈值不是越大越好，超过 128 之后就开始反噬。
• 拿两段划分去处理重复值很多的数据。全等值十万条，hoare 版本 3008.276 毫秒，三路划分 0.088毫秒，差了三万四千倍；这个坑在 OJ 上表现为超时，在本机表现为程序卡住，排查的时候先看数据分布，别急着怀疑编译器。
• 非递归版的栈开得太小，按理论深度开 64个区间对，遇到刻意构造的数据会溢出，而这个溢出不会有任何提示，只会把相邻的内存写坏。要么按最坏情况的两倍 n 开，要么在压栈前判断容量、满了就退回堆排序。

本篇总结（模拟面试问题）

问：快排为什么平均是 O(N log N)，什么情况下退化？

核心要点：每次划分把区间切成两段，两段长度接近时递归树高 log N，每层总代价 N，合起来是 N log N。退化发生在两段严重不平衡的时候，最典型的是基准值每次取到区间里的最小值或最大值，树高变成 N，总代价变成 N 的平方。已经有序、逆序、大量重复值都可能触发。

问：hoare 版本为什么必须先移动右侧游标？

核心要点：右侧游标停下时脚下的值一定不大于基准值，先走右边能让相遇点落在这个安全位置上；把基准值换到相遇点之后，左边全小、右边全大，划分才成立。先走左边的话相遇点可能落在比基准值大的位置，交换完基准值右边还藏着小的元素。

问：三数取中解决了什么问题，没解决什么问题？

核心要点：它解决了有序和逆序数据上的退化，因为左中右三点取中值，几乎不会连续取到极值。它没解决重复值造成的退化，等于基准值的元素仍然会全堆到一边，那种情况要换三路划分。

问：三路划分比两段划分快在哪，慢在哪？

核心要点：快在等于段整段归位，重复值多的时候递归层数大幅下降，全等值数据从三千毫秒降到零点零几毫秒。慢在每个元素要多比一次，随机数据上多出 8.6% 的开销，所以数据里重复值不多的时候两段划分仍然占优势。

问：内省排序的名字是什么意思，兜底是怎么做的？

核心要点：内省的意思是它在运行过程中观察自己的递归深度。深度超过两倍 log2 n 就说明划分一直不均衡，这时候把当前区间交给堆排序，堆排序的最坏情况是 N log N，于是整体的最坏情况也被压到 N log N。

问：快排能不能做到稳定？

核心要点：划分过程要在数组内部来回交换，交换会跨过若干相等的元素，稳定性保不住。想要稳定就换归并排序或者计数排序，它们的比较与回填顺序天然保持了相等元素的先后。

问：递归改非递归除了防栈溢出，还有什么好处？

核心要点：可以把栈放在堆上按需增长，也能在任务队列里控制处理顺序，比如先处理短的那一段、把长的压栈，这样栈的最大深度被压到 log N；还能顺便加上深度计数、超限换堆排序这些策略，递归版做同样的事要在参数里传一堆状态。

参考

• LeetCode 912 排序数组
• LeetCode 75 颜色分类
• LeetCode 215 数组中的第 K 个最大元素