如果你正在为快速排序的分区逻辑头疼大概率被下面这个问题卡过教程里写“i找大、j找小”你照着写完升序排序没有问题可题目一要求降序你把比较符号一翻程序反而开始乱套。另一篇教程又告诉你应该“i找小、j找大”。到底听谁的其实两个说法都成立区别只在于你的排序目标到底是升序还是降序以及你用的是哪一种分区写法。这篇文章就把“分区”和“排序方向”之间那层窗户纸捅破讲清楚升序下为什么是i找大、j找小降序下为什么要完全反过来。1. 先说结论分区不是在排序而是在给基准值“找座位”1.1 分区到底是干什么的快速排序的核心是每一轮从数组里挑一个基准值pivot然后通过一次分区partition操作把所有“应该排在基准值左边”的元素挪到左边所有“应该排在基准值右边”的元素挪到右边。注意这里的关键词应该排在基准值左边。这五个字不是数组自身决定的而是排序方向决定的。升序排序时小的数应该排在前面所以比基准值小的元素应该去左边比基准值大的应该去右边。降序排序时正好反过来比基准值大的元素应该去左边比基准值小的应该去右边。所以一次分区本质上就是给基准值找它在这个数组里的“最终座位”。座位在哪一侧取决于你想要的排列规则。搞清楚这一点分区的整个逻辑就立起来了。1.2 升序和降序是两套不同的“座位规则”我用一张表把两套规则摆出来对比排序目标基准值左边应该放什么基准值右边应该放什么左右两侧相对关系升序比基准值小的元素比基准值大的元素左小右大降序比基准值大的元素比基准值小的元素左大右小仔细看这个表分区代码里所有“找大”“找小”的说法都是从这两行推出来的。升序时为了让小的到左边、大的到右边扫描指针的任务就是找出“不该待在原侧”的元素。降序时任务镜像反转。1.3 座位规则决定了指针该找什么拿升序举例左边区域按理说应该全是小元素但数组初始是乱的里面可能混着大元素。i指针从左往右走它的任务就是揪出“混进左边区域的大元素”也就是找比基准值大的元素。右边的区域按理说应该全是大元素但里面可能混着小元素j指针从右往左走任务就是揪出“混进右边区域的小元素”也就是找比基准值小的元素。所以升序目标下i找大、j找小是自然而然的结果。一旦目标换成降序左边本该放大元素、右边本该放小元素i和j的找法就必须跟着反过来i找小、j找大。2. 升序分区的完整解剖i找大、j找小是怎么配合的2.1 先看一份能跑通的升序分区代码为了不让你被各种花哨模板带偏我用一种最朴素的“挖坑法”来演示。这种写法的优点是基准值一开始被存到变量pivot里原来的位置留成一个坑然后j先找小元素来填坑腾出右边的新坑再由i找大元素填到右边。循环往复最后把pivot填回i和j相遇的位置。def partition_asc(arr, left, right): pivot arr[left] # 基准值left位置先空出来当坑 i, j left, right while i j: # j从右往左找比pivot小的元素填到左边的坑 while i j and arr[j] pivot: j - 1 if i j: arr[i] arr[j] # 填坑 i 1 # i从左往右找比pivot大的元素填到右边的坑 while i j and arr[i] pivot: i 1 if i j: arr[j] arr[i] # 填坑 j - 1 arr[i] pivot # 基准值归位 return i代码里能看到明确的“i找大、j找小”分工j在找小于pivot的元素i在找大于pivot的元素。你可能觉得这个代码里的i和j跟标题里的“i找大、j找小”对上了但要注意这是升序版本。2.2 手把手推演一轮分区空讲不好理解直接上例子。数组[5, 1, 9, 3, 7, 2, 8, 4, 6]基准值取第一个元素5。第一轮j从右往左找小于5的arr[8]6不算arr[7]4算停住。把4填到左边的坑数组变成[4, 1, 9, 3, 7, 2, 8, 4, 6]注意下标7的位置变成了新坑。i从左往右找大于5的arr[1]1不算arr[2]9算停住。把9填到右边的坑数组变成[4, 1, 9, 3, 7, 2, 8, 9, 6]下标2成了新坑。第二轮j继续从右往左走arr[6]8不算arr[5]2算停住。把2填到左边坑数组变成[4, 1, 2, 3, 7, 2, 8, 9, 6]下标5成了新坑。i继续从左往右走arr[3]3不算arr[4]7算停住。把7填到右边坑数组变成[4, 1, 2, 3, 7, 7, 8, 9, 6]下标4成了新坑。第三轮开始前i4、j4循环条件i j已经不成立循环结束。最后把pivot5填回相遇位置数组变成[4, 1, 2, 3, 5, 7, 8, 9, 6]。验证一下基准值5左边是[4, 1, 2, 3]全部小于5右边是[7, 8, 9, 6]全部大于5。分区成功而且5的位置就是这一轮快排中它最终的位置。2.3 从推演里提炼“i找大、j找小”的准确含义推演过程里j停下并填充的元素是4、2——都是小于pivot的发生在左侧目的是把左侧的坑用“应该待在左边的小元素”填上。i停下并填充的元素是9、7——都是大于pivot的发生在右侧目的是把右侧的坑用“应该待在右边的大元素”填上。这就是“i找大、j找小”的本质升序时i负责发现不该留在左侧的大元素j负责发现不该留在右侧的小元素。一旦找到这样一对就通过填坑完成了交换两个元素各自归位。方向对了分区结束后的左右两侧必然满足“左小右大”的约束。3. 降序目标下的镜像翻转i找小、j找大3.1 降序的座位规则怎么改从第1章的座位规则表可以看出降序时基准值左边应该放大元素右边应该放小元素。所以当i从左往右扫描时它要找的不再是“比pivot大的元素”而是“比pivot小的元素”因为一个小元素混在左边区域是不合格的必须挪到右边去。同理j从右往左扫描时它要找的是“比pivot大的元素”因为它混在右边区域也不合格必须挪回左边。口诀整体翻转降序目标下i找小、j找大。3.2 降序分区代码与完整推演降序分区的代码只需要把升序版本里的两处比较符号反过来def partition_desc(arr, left, right): pivot arr[left] # 基准值left位置先空出来当坑 i, j left, right while i j: # j从右往左找比pivot大的元素填到左边的坑 while i j and arr[j] pivot: j - 1 if i j: arr[i] arr[j] i 1 # i从左往右找比pivot小的元素填到右边的坑 while i j and arr[i] pivot: i 1 if i j: arr[j] arr[i] j - 1 arr[i] pivot # 基准值归位 return i用同一个数组[5, 1, 9, 3, 7, 2, 8, 4, 6]推演第一轮j从右往左找大于5的arr[8]6算停住。把6填到左边坑数组变成[6, 1, 9, 3, 7, 2, 8, 4, 6]下标8成了新坑。i从左往右找小于5的arr[1]1算停住。把1填到右边坑数组变成[6, 1, 9, 3, 7, 2, 8, 4, 1]下标1成了新坑。第二轮j继续从右往左走arr[7]4不算arr[6]8算停住。把8填到左边坑数组变成[6, 8, 9, 3, 7, 2, 8, 4, 1]下标6成了新坑。i继续从左往右走arr[2]9不算arr[3]3算停住。把3填到右边坑数组变成[6, 8, 9, 3, 7, 2, 3, 4, 1]下标3成了新坑。第三轮j继续从右往左走arr[5]2不算arr[4]7算停住。把7填到左边坑数组变成[6, 8, 9, 7, 7, 2, 3, 4, 1]下标4成了新坑。i继续从左往右走arr[4]7不算arr[5]5不对i从3继续arr[4]已经被填成了77 5所以i继续走到下标5arr[5]2 5这才是要找的小元素。注意这时候i5、j4i j已经不成立循环结束。最后把pivot5填回i5的位置数组变成[6, 8, 9, 7, 5, 2, 3, 4, 1]。验证基准值5左边是[6, 8, 9, 7]全部大于5右边是[2, 3, 4, 1]全部小于5。降序分区成功。3.3 一张表说清升序/降序指针分工的差异排序目标i从左往右找什么j从右往左找什么填坑方向分区约束升序找比pivot大的元素找比pivot小的元素小填左坑、大填右坑左侧≤pivot右侧≥pivot降序找比pivot小的元素找比pivot大的元素大填左坑、小填右坑左侧≥pivot右侧≤pivot这张表就是整个问题的标准答案。你以后写分区函数不必背“i找大、j找小”这个口诀本身而是对照这张表问自己一句pivot左边应该放什么答案是“小”就用升序版答案是“大”就用降序版。4. 方向搞反之后的翻车现场与五分钟定位法4.1 翻车现场一结果“看似有序又不太对”我当年第一次把降序分区写成升序版跑出来的数组不是完全升序也不是完全降序而是局部有序、整体错乱。比如上面那个数组降序预期应该是[9, 8, 7, 6, 5, 4, 3, 2, 1]用错方向跑完很可能得到类似[5, 6, 8, 7, 9, 2, 3, 4, 1]这种诡异的序列。原因在于分区方向与递归方向其实是一套组合。升序分区会把基准值归到“左边是小、右边是大”的位置递归再对左右两侧继续做升序处理降序分区则让基准值归到“左边是大、右边是小”的位置。如果你把分区里的比较方向改了但递归的排序目标没同步改左右两侧的排列规则就会互相打架结果自然不伦不类。4.2 翻车现场二死循环和递归栈溢出方向写反时更隐蔽的问题是死循环。分区结束时i和j的相遇位置会变得非常靠边导致基准值归位后左右子区间大小几乎不减。比如你期望每次分区把数组切成两部分结果基准值每次都被放到数组的一端递归深度直接变成O(n)数据量一大就栈溢出小数据量则表现为程序卡死。这有点像你把房间里的物品按“重要程度”整理但整理规则标反了你每次挑出的“最该放门口的东西”其实是“最该放床底的东西”整理半天门口那堆东西始终整理不干净永远有东西被来回搬运。4.3 翻车现场三排序结果局部有序、全局混乱还有一种更迷惑的翻车有时候小数组跑出来看着像部分有序你以为只是边界条件写错就去调递归区间调来调去却没用。这是因为方向错误不是边界问题你在错误的“座位规则”下无论怎么切分左右区间元素的大小关系都满足不了目标顺序。判断这类问题最有效的方法不是调代码而是做一次纸面推演像上面那样手动跑一轮分区看基准值左右两侧到底满不满足对应的约束。4.4 五分钟定位打印分区后的数组遇到排序结果不对先别急着猜在分区函数结束的位置打印数组和返回值然后人工检查三件事基准值是不是落在返回下标位置。基准值左边是否全部满足“该在左边”的约束升序看是否≤pivot降序看是否≥pivot。基准值右边是否全部满足“该在右边”的约束。如果前两项有任意一项不满足基本就是分区方向或比较符号写反了。如果三项都满足问题才可能出在递归区间或调度逻辑上。# 快速检查伪代码 def debug_partition(arr, left, right): pos partition_asc(arr, left, right) print(arr, pos , pos, pivot , arr[pos]) # 人工核对arr[left:pos] 是否 ≤ arr[pos]arr[pos1:right1] 是否 ≥ arr[pos]这一步能帮你把“感觉代码不对”变成“明确知道哪里不对”。5. 为什么另一篇教程说“i找小、j找大”也对两种分区写法辨析5.1 两种常见 partition 的指针角色你去看网上讲快排的文章会发现有人写“i找大、j找小”有人写“j从前往后找小”。这两种说法看着矛盾其实是两套不同的经典分区模板。我上面演示的挖坑法属于“首尾双指针”流派i和j一左一右相向而行通过填坑完成交换。另一套流传很广的写法叫Lomuto分区基准值通常选最右端一个扫描指针j从前往后走遇到比基准值小的元素就把它和“小区间边界指针i”指向的位置交换。在Lomuto写法里升序排序时j确实全程在“找小”然后把小元素往数组前面搬。这和你看到的“i找大、j找小”当然不一样——因为两套写法对i和j的定义完全不是一回事。5.2 挖坑法与 Lomuto 法的核心差异对比项挖坑法首尾双指针Lomuto法快慢指针i的角色从左往右找大/小元素去填右边坑记录“小区间”的右边界j的角色从右往左找小/大元素去填左边坑从前往后扫描找基准值小的元素基准值位置通常选left通常选right升序时j在找什么找比pivot小的元素从右往左找比pivot小的元素从左往右返回位置pivot归位的下标i小区间与大兴区间的分界iLomuto的代码长这样def partition_lomuto_asc(arr, left, right): pivot arr[right] i left for j in range(left, right): if arr[j] pivot: arr[i], arr[j] arr[j], arr[i] i 1 arr[i], arr[right] arr[right], arr[i] return i这套写法中i不是“找”任何东西它只是小元素的落点真正一路找小元素的是j。所以网上教程如果基于Lomuto模板说“找小”并不是在否定“i找大、j找小”而是在说另一套指针体系。5.3 怎么判断教程里的 i/j 到底在找什么看任何一篇讲快排的文章先别急着背口诀先确认三件事基准值选的是left还是right。i和j的初始位置分别在哪。内层循环里比较符号长什么样。确认完这三点你就能还原出作者用的是挖坑法还是Lomuto法再对照自己的目标方向去理解。最忌讳的是把两套模板的指针职责混在一起一会儿记这个口诀一会儿套那个模板最后代码写得四不像。我的建议是固定使用一套模板把它的升序、降序两种形式都写熟。比如你固定用挖坑法升序就是i找大、j找小降序就是i找小、j找大你固定用Lomuto升序就记“j找小i是小元素落点”降序就记“j找大i是大元素落点”。混用才是最大风险源。6. 写分区代码必注意的三个边界细节6.1 循环里的等号怎么处理才不会死循环挖坑法的内层循环我写的是arr[j] pivot和arr[i] pivot也就是等于pivot的元素会被跳过。这样做的目的是避免当数组里大量元素等于pivot时i和j在同一个位置反复交换、死循环。如果你把条件改成严格的arr[j] pivot和arr[i] pivot意思是等于pivot的元素也可以停下来填坑这在某些情况下也能用但要注意它可能导致相同的元素被搬运来搬运去。对新手来说用带等号的跳过写法更稳妥不容易踩死循环的坑。6.2 递归区间传错一格的后果很多小白写完分区函数在快速排序的递归调用里把区间写成了quickSort(arr, left, i)而不是quickSort(arr, left, i - 1)。这会造成基准值一直留在下一次排序的区间里递归永远无法收敛最终栈溢出。记住分区函数返回的下标位置上的元素已经是最终位置不应该再参与排序。所以递归是quickSort(arr, left, pos - 1)和quickSort(arr, pos 1, right)。如果你用的是Lomuto模板返回的i同样要这样处理。6.3 纸面自测与断言验证我在教学和自查时有个习惯写完分区函数一定用三个小用例做纸面测试:乱序数组如[5,1,9,3,7,2,8,4,6]验证普通情况。全部重复数组如[3,3,3,3,3]验证等号和死循环问题。已经有序的数组如[1,2,3,4,5]验证退化情况这时候分区的返回位置通常会在数组最左或最右端递归深度会退化。在代码里你还可以加一条assert在分区结束后检查“左侧约束”和“右侧约束”一旦不满足立刻报错def check_partition(arr, left, right, pos, increasingTrue): for k in range(left, pos): if increasing and arr[k] arr[pos]: raise AssertionError(左侧出现了大于pivot的元素) if not increasing and arr[k] arr[pos]: raise AssertionError(左侧出现了小于pivot的元素) for k in range(pos 1, right 1): if increasing and arr[k] arr[pos]: raise AssertionError(右侧出现了小于pivot的元素) if not increasing and arr[k] arr[pos]: raise AssertionError(右侧出现了大于pivot的元素)这条断言能帮你把方向性和边界问题一次性暴露出来。6.4 库函数排序的“方向”怎么理解搞懂了分区里的方向再看各语言内置排序接口的方向其实就顺了。C的sort允许你自定义比较器返回true表示第一个参数应排在第二个参数前面Python的sort有参数reverseTrueJava的Comparator通过返回值正负决定先后。这些底层机制本质上都是在定义同一件事什么叫“该排在前面”。你把“座位规则”想清楚再看这些API的文档就不会被升序降序绕晕。我自己现在写快排还会在分区函数第一行注释里写清楚当前用的是升序还是降序以及“左边该放什么”。这个习惯帮我避过很多次把符号改错的低级错误。排序问题的本质从来不是记住某个口诀而是搞清楚你要把元素送到哪个方向去。