“i找大、j找小适配升序目标”还是“i找小、j找大适配降序目标”——如果你看到这句话也愣了一下说明你已经在快排分区的坎上卡过至少一次了。我见过不少人背分区代码背得滚瓜烂熟可一旦要求输出降序整个人就像被按了暂停键指针到底该找大的还是小的要不要把i和j的起始位置对调基准值换到哪一边结果越改越乱最后只能靠死记硬背应付过去。这篇笔记不聊别的就把分区的目的、排序的方向、以及双指针各找什么这三件事的因果关系彻底捋一遍。看完你不仅能分清升序降序的分区写法还能理解为什么这样写是对的以后不管是手写快排还是改排序方向都不会再靠猜。内容适合刚学完基础排序的小白、准备算法面试但一紧张就忘方向的开发者也适合想给同学讲明白快排的助教们。1. 为什么分区、方向、指针这三样总让人打结1.1 分区的目的不是整体排序而是让基准值归位很多人对快排的误解是从“分区”这个词开始的。他们以为分区是在做排序动作跑完一趟整个数组就应该有点“排好”的样子。实际上一趟分区只干一件事把一个基准值放到它最终该待的位置。为什么一趟只放一个数最后整个数组却能有序因为快排是递归的。每次分区选一个基准pivot然后让所有小于等于pivot的元素跑到它左边所有大于等于pivot的元素跑到它右边。请注意这句话的分量pivot一旦完成这一步它的位置就再也不会变了。原因很简单——左边已经没有比它大的元素右边已经没有比它小的元素如果之后整个数组还要有序pivot没必要再向左或向右挪动哪怕一格。接下来对pivot左边的子区间和右边的子区间各自重复这个过程左区间选一个基准放到位右区间选一个基准放到位。每一趟解决一个元素的最终位置递归下去每个元素都会在某一次分区中当基准被“钉死”在正确位置上。到子区间只剩一个元素时它天然就是有序的。这就是快排的核心逻辑——分治归位。用一个生活类比帮助理解想象一排人按身高排队。你从中间拉出一个中等身高的人当标杆让他站在一个临时位置不动然后让所有比他矮的人站到他左边所有比他高的人站到他右边。标杆的位置先固定下来剩下的人再分成左右两拨重复这个流程。整个过程不是一次排完的而是每轮固定一个“标杆”最终所有人的位置都确定下来。所以分区里的“左小右大”或者“左大右小”只是一个过程状态不是最终目标。搞清楚这一点后面理解排序方向会轻松很多。1.2 排序方向的本质只是改变了“哪一侧该放什么”搞清楚分区目的之后再看“排序方向”就简单了。升序意味着最终结果从小到大那左区该放小元素右区该放大元素降序意味着最终结果从大到小那左区该放大元素右区该放小元素。就这么点区别。但很多人卡住的原因恰恰在这里他们试图从“指针从哪里走”去记住方向规则而指针的行动路线从来只有一个版本——i永远从左往右走j永远从右往左走升序降序都是这样方向不会变。会变的只是它们在途中判断“停下”的标准。什么标准就是“这个元素是不是不该待在我这一侧”。升序时左区该放小元素i从左往右走遇到一个比基准大的元素就说明它混进了左区该停下等待被换走右区该放大元素j从右往左走遇到一个比基准小的元素说明它混进了右区也该停下。降序时左区该放大元素i遇到比基准小的元素才停下右区该放小元素j遇到比基准大的元素才停下。一句话总结指针的走向永远不变变的是它们要找的猎物。猎物是什么由“这一侧该放什么”决定。你只要在写代码前想清楚“当前排序方向下左区该放什么”两个while循环就不会写反。2. 升序目标i找大、j找小是怎么绕过来的2.1 双指针的“猎物法则”升序场景下分区要得到的目标形态是左区 pivot 右区。把这句话拆开看左区应该欢迎所有小于等于pivot的元素不应该出现大于pivot的元素。所以i从左往右检查时一旦发现大于pivot的元素就停——i找的是大数。右区应该欢迎所有大于等于pivot的元素不应该出现小于pivot的元素。所以j从右往左检查时一旦发现小于pivot的元素就停——j找的是小数。为什么找到之后要交换因为一个是该去右边却待在左边的大数一个是该去左边却待在右边的小数两者一交换各自去到了该去的位置左区和右区各多了一个正确元素。两个指针继续往中间走直到相遇整个区间就被“扫”了一遍。这里有个容易忽略的不变式每交换一次i左边所有元素已经确认小于等于pivotj右边所有元素已经确认大于等于pivot。所以交换之后i才可以放心右移j才可以放心左移不需要回退重看。这个不变量是双指针分区正确性的基石也是“i找大、j找小”这句话背后的原理。2.2 手把手走一遍升序分区拿一个具体例子走一遍。数组是[5, 2, 8, 3, 1, 7, 4]选最左边的5作为基准i 0j 6。第一轮循环j先动从下标6往左找“小于5”的数。arr[6] 44确实小于5j停在6。i再动从下标0往右找“大于5”的数。arr[0] 5升序分区里5不大于5继续右移arr[1] 2继续右移arr[2] 88大于5i停在2。i j交换arr[2]和arr[6]。数组变成[5, 2, 4, 3, 1, 7, 8]。第二轮循环j从刚才停的下标6继续往左找小数arr[6] 8不小于5j到5arr[5] 7不小于5j到4arr[4] 1小于5j停在4。i从刚才停的下标2继续往右找大数arr[2] 4不大于5i到3arr[3] 3不大于5i到4。此时 i j循环结束。最后把基准值arr[0] 5和相遇点arr[4] 1交换数组变成[1, 2, 4, 3, 5, 7, 8]。位置4就是5的最终位置左边全是小于5的数右边全是大于5的数。虽然左右两边内部还没完全排好但5已经归位接下来递归处理[0..3]和[5..6]即可。注意一个实操细节每一轮内层循环都要从上一轮停下的位置继续而不是从区间的端点重新开始。这是因为交换后i左侧和j右侧的元素已经检查合格从端点重来纯属浪费。2.3 为什么代码里必须先动j再动i网上大部分快排模板都长这样// 升序分区基准取最左 int partition(vectorint arr, int left, int right) { int pivot arr[left]; int i left, j right; while (i j) { // j先动找小于pivot的 while (i j arr[j] pivot) j--; // i后动找大于pivot的 while (i j arr[i] pivot) i; if (i j) swap(arr[i], arr[j]); } // i j基准归位 swap(arr[left], arr[i]); return i; }很多初学者会问两个内层while对调一下先动i再动j不行吗答案是不行会挂。用一个反例说明。数组[3, 5, 1, 8, 2]基准取最左的3。正确版本先j后i最终得到[2, 1, 3, 8, 5]3在正确位置。如果把两个内层循环次序对调先跑ii找大数arr[0] 3不大于3i到1arr[1] 5大于3i停在1。j找小数arr[4] 2小于3j停在4。交换arr[1]和arr[4]数组变成[3, 2, 1, 8, 5]。继续i从1走arr[1] 2不大于3i到2arr[2] 1不大于3i到3arr[3] 8大于3i停在3。j从4走arr[4] 5不小于3j到3。i j 3交换arr[0] 3和arr[3] 8得到[8, 2, 1, 3, 5]。看到了吗基准3左边出现了8分区失败。为什么先动j才安全因为最后基准值要和相遇点交换而“相遇点”必须是一个属于左区的元素小于等于pivot。j从右往左找的恰好就是这类元素所以先让j找到并停在某个位置上哪怕之后i也走到这个位置这个点的“底色”也是满足左区条件的。反过来如果先让i跑i会停在一个大于pivot的元素上后面j再找过来的小数可能落在i的右侧最终相遇点很可能落在一个大数上。基准值换过去大数就被带进了左区。先动j这个顺序本质上是为最后一次“基准值归位”做安全保障。3. 降序目标i找小、j找大套路原样平移3.1 降序的猎物法则降序分区的目标形态是左区 pivot 右区。把升序的逻辑镜像一下左区现在该放大数不该出现小于pivot的元素。所以i从左往右检查时一旦发现小于pivot的元素就停——i找的是小数。右区现在该放小数不该出现大于pivot的元素。所以j从右往左检查时一旦发现大于pivot的元素就停——j找的是大数。看出对称性了吗升序时i找大、j找小降序时i找小、j找大。字面上完全相反但背后的逻辑完全一致i找的是“左区不该存在的元素”j找的是“右区不该存在的元素”。排序方向变了左区该放什么变了找的猎物自然跟着变。这个角度特别重要。只要记住“先想左区该放什么”就不用死背“升序i大j小降序i小j大”这种口诀。口诀是结果不是原因。3.2 用同一组数据走一遍降序分区还是[5, 2, 8, 3, 1, 7, 4]基准取最左的5i 0j 6。第一轮循环j先动从右往左找“大于5”的数。arr[6] 44不大于5j到5arr[5] 7大于5j停在5。i后动从左往右找“小于5”的数。arr[0] 5不小于5i到1arr[1] 2小于5i停在1。i j交换arr[1] 2和arr[5] 7数组变成[5, 7, 8, 3, 1, 2, 4]。第二轮循环j从5继续找大数arr[5] 2不大于5j到4arr[4] 1不大于5j到3arr[3] 3不大于5j到2arr[2] 8大于5j停在2。i从1继续找小数arr[1] 7不小于5i到2。i j 2循环结束。交换arr[0] 5和arr[2] 8得到[8, 7, 5, 3, 1, 2, 4]。位置2是5的最终位置左边8和7都大于5右边3、1、2、4都小于5。递归处理左右区间后最终得到降序结果[8, 7, 5, 4, 3, 2, 1]。走完这一趟你会发现代码流程和升序时一模一样只有内层循环的比较符号反过来了。3.3 升序降序对比只改两处符号降序分区代码// 降序分区基准取最左 int partition(vectorint arr, int left, int right) { int pivot arr[left]; int i left, j right; while (i j) { // j先动找大于pivot的 while (i j arr[j] pivot) j--; // i后动找小于pivot的 while (i j arr[i] pivot) i; if (i j) swap(arr[i], arr[j]); } swap(arr[left], arr[i]); return i; }对比升序版本真正改动的只有两行场景j跳过什么i跳过什么升序arr[j] pivot继续向左跳找小的arr[i] pivot继续向右跳找大的降序arr[j] pivot继续向左跳找大的arr[i] pivot继续向右跳找小的也就是“什么元素可以留在原位、继续移动指针”的规则反过来了。快速排序的外层函数完全不用动void quickSort(vectorint arr, int left, int right) { if (left right) return; int p partition(arr, left, right); quickSort(arr, left, p - 1); quickSort(arr, p 1, right); }这里顺带纠正一个常见误解排序方向不是靠“递归时先处理左边还是先处理右边”决定的。递归左右顺序怎么安排都不影响最终升序还是降序它只是分治的遍历顺序。方向只由分区内的比较符号决定。4. 边界条件、相等元素和递归区间的坑4.1 内层循环的 ij 保护一次都不能省标准模板里每个内层while都带了一个i j条件它的作用是什么防止j一路向左冲过头或者i一路向右冲过头。但更重要的是它保证了两个指针在交错之后立即停止扫描。看一个极端例子数组[1, 2, 3, 4, 5]升序基准取最左的1。假设内层循环没有i j保护while (arr[j] pivot) j--; // 危险写法j从4开始arr[4] 5 1j到3arr[3] 4 1j到2arr[2] 3 1j到1arr[1] 2 1j到0arr[0] 1 1j到-1。数组越界程序崩溃。即使没越界指针也会跑到已经处理过的区域把前面分区建立好的不变量破坏掉。所以两个内层while的i j都要和比较条件写在一起形成“有边界地找猎物”的模式。这是双指针夹逼的标配不是可选优化。4.2 相等元素为什么不能用严格大于小于核心两个while里升序用的是和也就是遇到等于pivot的元素指针直接穿过不停留。很多人会好奇我用和行不行试试看。升序代码如果写成while (i j arr[j] pivot) j--; while (i j arr[i] pivot) i;遇到数组里有多个等于pivot的元素时问题就来了。比如[4, 4, 4]基准是4j从右往左找小于4的数找不到一路到i的位置i从左往右找大于4的数也找不到一路到j的位置。两个内层循环在等于基准的元素上互相“让路”最终i和j在中间相遇勉强还能结束。但如果换成其他模板写法或者基准取值改到最右两个等于基准的元素可能会被反复交换导致死循环。更关键的是用严格比较时“等于pivot”的元素既不被i选中也不被j选中相当于它们被排除在交换之外。这使得基准值归位时等于它的元素可能散落在左右两侧。虽然最终有序性不被破坏但分区的平衡性和小区间稳定性都会受影响。标准模板用和等于基准的元素会被指针直接穿过分区过程更干净也不容易出现异常卡顿。大量重复元素的场景还有更优解比如三路分区但这篇笔记不展开。先把等号处理对至少能保证不出错。4.3 递归区间怎么切才不会漏排或死循环partition返回的是基准值最终所在下标p。递归时处理左区间[left, p-1]和右区间[p1, right]基准本身不再参与后续排序。为什么因为pivot已经处在它最终的位置上左区全小于等于它右区全大于等于它。再把它放进任意一个子区间里递归等于让一个已固定位置的元素反复参与比较和交换既浪费时间还可能在两个元素时造成原地交换、递归不收敛的情况。如果partition返回的位置恰好是区间端点比如p等于left那左区间就是[left, left-1]是个空区间。此时quickSort开头的if (left right) return;就直接兜住了不需要单独判断。这样一来空区间和单元素区间统一被函数开头的退出条件处理掉递归一定能收敛。区间切分规则跟升序降序完全无关所以quickSort主体从升序切到降序时一个字符都不用改。5. 常见问题排查与五分钟记忆法5.1 故障速查表把实际操作中最容易踩的坑整理成一张表遇到问题时按图索骥现象可能原因排查方法分区后基准左边出现比基准大的数两个内层循环顺序写反先跑了i把j的while移到前面保证相遇点是左区元素程序崩溃或数组越界内层循环少了i j保护两个内层while条件里都补上i j排序结果是反的升序降序的符号没翻或翻错位置检查分区内两个比较符号是否和目标方向匹配降序结果局部正确整体不对只改了递归左右顺序没改分区比较符号排序方向由分区内比较符号决定递归顺序无关数组大量重复时极其缓慢或死循环严格比较符号导致相等元素卡住改成和或考虑三路分区递归层数过深接近栈溢出基准每次都取到最大或最小分区严重失衡改用随机基准或三数取中第二行和第四行是我见过频率最高的两类问题。第二行直接导致程序崩溃第四行则是思维惯性陷阱——很多人把“降序”等同于“先递归右边”结果方向根本没变过来。5.2 五分钟记忆法先把左区规则写在注释里我在实际带人写快排时多次强调一个习惯写partition之前先在函数顶部写一行注释把这趟分区想让左区变成什么样写清楚。升序就写// 升序左区放 pivot 的元素右区放 pivot 的元素降序就写// 降序左区放 pivot 的元素右区放 pivot 的元素有了这行注释两个while的推导就是白送的了。i从左往右检查遇到“不应该出现在左区”的元素就停j从右往左检查遇到“不应该出现在右区”的元素就停。你把注释当成“猎物通缉令”指针就是在执行这份通缉令。浓缩成一句话就是升序i找大、j找小降序i找小、j找大指针走向永远不变变的是它们逮什么猎物。这句话足够你考前临时抱佛脚但真要考试或面试我建议你按“左区该放什么”去现场推导比回忆口诀靠谱得多。5.3 几个实战心得第一先从纸上走小数组。绝不要直接盯着代码理解快排。拿5到7个元素的数组手动执行一遍完整分区流程把i、j每一步停在哪个位置记下来。动手走一趟比看十遍图解都管用。我自己当初就是用这个方法彻底搞懂“先动j”的原因。第二面试或比赛时如果真忘了方向用Lomuto单指针分区兜底。它的逻辑简单得多j负责遍历整个区间遇到符合条件的元素就跟i位置的元素交换i维护左区边界。升序时“比基准小就纳入左区”降序时“比基准大就纳入左区”只要比较符号写对不会出现双指针那种“谁先动”的坑。代价是常数性能稍差但正确率优先。第三遇到大量重复元素基础双指针版本会退化得很厉害。这时候该升级的是三路分区把等于基准的元素单独放中间一区左右两个子区间只处理严格小于和严格大于的部分。这跟升序降序的方向逻辑无关但如果你经常做排序相关题目值得在掌握基础版本之后继续研究。第四写代码前先想清楚pivot取哪个位置。本文所有模板都取最左元素当基准这有一个已知弱点如果数组原本已经有序分区会严重失衡快排退化成O(n²)。实际工程中建议随机选基准或者从首、中、尾三个位置取中位数当基准。这个优化和排序方向不冲突升序降序都一样。快排分区的方向问题本质上是“因果链”没建立起来你记住了i找大、j找小但没有把“为什么这样找”记住。一旦建立起来升序降序在你眼里就是同一个模板的两个镜像而已。我自己最初学的时候也在这个问题上折过好几回后来每次写快排前先写“左区该放什么”的注释从此再没写反过。希望这篇笔记能让你一次性跨过这道坎。