快速排序指针移动方向详解：从分区目标推导i找大j找小

快排学到指针移动方向的时候，我卡了整整一个晚上。网上教程要么直接给口诀，要么默认你懂分区目标，死活想不明白“i找大、j找小”和“i找小、j找大”到底怎么选。后来我拿笔把两个方向都推了一遍，又把key取左、key取右的情况都试了，才彻底悟了：指针移动方向根本不靠背，它完全由“分区目的”和“基准值位置”推出来。这篇笔记就把这套推理过程完整写出来，适合正在学快速排序、被Hoare分区法绕晕的初学者，也适合想彻底搞懂为什么“先从j开始”的老读者。看完你会得到一个通用的判断方法，以后遇到升序、降序，不管key在左还是右，都不会再迷路。

1. 先搞懂分区的目的，指针方向才有意义

1.1 分区的核心：单趟排序到底在追求什么

快速排序的核心思想用一句话说：每一次选一个基准值（简称key），把数组分成左右两部分，让左边的元素都比key小（升序时），右边的元素都比key大，然后把key放到中间这个正确位置。这样一趟下来，key这个元素就“归位”了，它不再需要参与后续排序。

这里的关键认知是：单趟分区不追求整个数组有序，只追求“key到达它最终该待的位置”。左边的元素整体小于key，右边的元素整体大于key，但左右内部仍然无序。后续通过递归，不断对左右两个子区间执行同样的分区操作，才最终变成完全有序。

这个“局部归位”的思路就是我理解的整个快排的骨架。所有那些看着眼花缭乱的代码写法——Hoare法、挖坑法、前后指针法——本质上都是在做同一件事：把小的换到key左边，把大的换到key右边。不同的只是实现手段。

想通这一点之后，再看“i找大、j找小”这两个口诀，就有了推理的起点。方向不是凭空设定的，分区的目的决定了我们凭什么标准去找目标元素。

1.2 目标顺序决定“找大”还是“找小”

一句话结论先放这里：

• 升序目标：左边的最终状态是小值在左、大值在右，所以指针要找的对象是“左边的大值”和“右边的小值”。
• 降序目标：目标方向反过来，最终状态是大值在左、小值在右，所以指针要找的对象是“左边的更大值”和“右边的更小值”。

我一开始看这个总觉得像绕口令。后来把“找”这个动作和“换”这个动作联系起来，才真正理解。想象你面前有一堆扑克牌，你想把小牌放左边、大牌放右边。那你需要做的是：从左半部分里找到一张误入歧途的大牌，从右半部分里找到一张误入歧途的小牌，然后交换它们。对吗？

左边需要放小牌，所以我要把左边不该待着的大牌找出来；右边需要放大牌，所以我要把右边不该待着的小牌找出来。这不就是“左找大、右找小，然后交换”吗？

降序同理。目标是左边放大牌、右边放小牌，那我自然要从左边找小牌、从右边找大牌，交换之后才符合降序的目标。

这就是标题里那个问题的本质：你用哪根指针找大、哪根指针找小，完全由排列目标决定。升序就是“左找大、右找小”，降序就是“左找小、右找大”。千万不要把口诀机械记忆成“必须是i找大、j找小”，那是升序目标下的特例。

不过这里还有个隐藏前提：谁在左、谁在右。Hoare经典写法里，i是左指针、j是右指针，所以标题里的那两个选项——“i找大、j找小适配升序目标”和“i找小、j找大适配降序目标”都是成立的，因为i在左、j在右。

如果我叫a指针和b指针，那表述就变成“左指针找大、右指针找小适配升序目标”。所以准确来说，不是i固定找大，而是“左指针在升序时找大、右指针在升序时找小”。这一点必须先澄清，否则换个变量名你就懵了。

2. “i找大、j找小”与“i找小、j找大”的运行逻辑

2.1 升序目标：i找大、j找小是怎么跑起来的

以最常见的Hoare分区法为例，假设数组是 [5, 3, 8, 6, 2, 7, 1, 4]，key取最左边的元素5。

指针i从左边第二个位置开始向右走，j从最右边向左走。在升序目标下，左侧区域最终应该放小值，右侧区域最终应该放大值。所以：

• i的任务是从左往右，找到一个比key大的元素。因为左侧区域不该有大值，发现了就要让位。
• j的任务是从右往左，找到一个比key小的元素。因为右侧区域不该有小值，发现了就要把它换回左边。

给出的定义是：i先找大，找到后停下来；j找小，找到后停下来。两个位置上的元素交换。这样一来，那个大的值一下子被扔到右边去了，那个小的值一下子被请回左边来了。是不是正好顺应升序的方向？

用生活类比：想象两队人马要按高矮排列，矮个子去左边排队，高个子去右边。i就是左边队伍的引路员，看到左边混进了一个高个子就喊“停”；j是右边队伍的引路员，看到右边混进来一个矮个子就喊“停”，然后把这两个人调换岗位。这一波操作之后，队伍离最终目标近了一步。

我在初学的时候，总是把“找大”“找小”理解成让指针去找符合条件的位置，但其实更准确的理解是“找到某一个值之后停下来，等待交换”。找大不是目的，交换才是目的。把这个心态转换过来后，看代码会清晰很多。

2.2 降序目标：为什么变成i找小、j找大

降序排列的目标是左边大、右边小。如果我们继续用“i找大、j找小”，会发生什么？

i从左往右找到一个大值，停；j从右往左找到一个小值，停。交换这两个位置。交换完成后，左边的这个位置现在是小值，右边的这个位置现在是大值。让我把这句话再看一遍——这种交换动作等于把一个小值放进了左区，把一个大值放进了右区。这是降序目标下我们想要的效果吗？恰恰相反，这就是升序逻辑。如果对整个数组都这样做快排，最终整体变成升序，跟降序目标正好背道而驰。

所以要实现降序，必须把交换的逻辑反一反，让左边变成大值聚集地、右边变成小值聚集地。怎么做？

• i从左往右，找到比key小的元素，停下来。
• j从右往左，找到比key大的元素，停下来。
• 交换i位置和j位置的值。

这个交换的效果是：小值被移到右边区域，大值被移到左边区域。这就完全匹配降序目标了。所以标题里问的“i找小、j找大适配降序目标”，回答是：完全正确，而且这才是正确组合。

我在自己学习的时候，喜欢把升降序理解成“对分区目标的一句话指令”。升序时，往左边塞小值；降序时，往左边塞大值。指针的找法由这个指令反向推导，根本不用背。

2.3 用一个完整例子验证两种方向的差异

我实际推演过一个例子。为了看得清楚，我用5个元素的数组：[4, 1, 3, 5, 2]，key取4。

升序版本，i找大、j找小：

• i从第二个元素开始走，1比4小，继续；3比4小，继续；5比4大，i停在这里（位置3，值是5）。
• j从右往左走，2比4小，j停在这里（位置4，值是2）。
• 交换5和2，数组变成 [4, 1, 3, 2, 5]。
• 继续移动，i再向右走，走到下标4发现越界，与j相遇于位置3（值是2）。此时key是位置0的4。
• 按Hoare规则，最后把key和j位置（相遇位置）的值交换：4和2交换，数组变成 [2, 1, 3, 4, 5]。
• 4的左边是2、1、3，都小于4；右边是5，大于4。分区成立。

降序版本，i找小、j找大：

同样的数组 [4, 1, 3, 5, 2]，key还是取4，目标是从大到小排列。

• i从左往右，找比4小的值。1比4小，i停在位置1（值是1）。
• j从右往左，找比4大的值。2比4小，继续；5比4大，j停在位置3（值是5）。
• 交换1和5，数组变成 [4, 5, 3, 1, 2]。
• i继续往右走，3比4小，i停在位置2（值是3）。
• j继续往左走，5比4大，但j已经越过了位置3，继续走，3比4小，不满足“找大”，继续走，走到位置2和i相遇（值是3）。
• 把key位置的值4和相遇位置的值3交换，数组变成 [3, 5, 4, 1, 2]。
• 此时4左边是3和5，并不全大于4，看起来好像没成功？问题出在哪里？

我仔细又推了一遍，问题出在“i找小”停下来的位置，和“j找大”的停止条件。这个例子比较小，在降序情况下，key取左端点时，分区逻辑更强调“从j先走”（后面细讲），而我的手动推演里没注意这个顺序。

重新走一遍正确的降序推演：

数组 [4, 1, 3, 5, 2]，key取左端点4。降序目标，需要左边最终都大于key，右边最终都小于key。因为key在左边，最后一步要把key换到正确位置，这个正确位置要求在它左边都是大值、右边都是小值。关键推演要注意“先从j开始找大”。

• j从右往左走，找比4大的值。2比4小，继续；5比4大，j停在位置3（值是5）。
• i从左往右走，找比4小的值。走到位置1时，1比4小，i停在位置1（值是1）。
• 交换i位置和j位置的值：1和5交换，数组变成 [4, 5, 3, 1, 2]。
• j继续从当前位置向左走，找比4大的值。5比4大，但已经走过位置3了，再往左是位置2的值3，3比4小，不满足找大，继续走，走到位置1时和i相遇（该位置现在值是5，是在上一步交换过来的）。
• 因为key仍留在最左边位置0，最后把key和相遇位置的值交换：4和5交换，数组变成 [5, 4, 3, 1, 2]。
• 现在4的左边是5，大于4；右边是3、1、2，都小于4，左边大右边小的降序分区目标达成。

这次推演成功了。两次推演的差异恰好说明了j先走的必要性，以及指针停止条件的细节决定了单趟分区的正确性。升降序目标不同时，最后交换key的那个值，必须满足“与key交换后符合方向要求”这个条件。

3. 实操中真正决定成败的细节

3.1 为什么Hoare版通常坚持“先从j开始”

我真切体会过，即使知道“i找大、j找小”，如果顺序反了，同样会出错。Hoare版本里一个雷打不动的规则是：key取最左边的元素时，先从右边（j）开始移动。反过来，key取最右边的元素时，先从左边（i）开始移动。

为什么？因为最终要把key交换到中间位置，这个“中间位置”实际上就是i和j相遇的位置。这个相遇位置的值，必须满足一个关键条件：换到左边来之后，依然符合“左边小于key”这个约束。

我逐步来分析。key在左边时，最后一步逻辑是把key与相遇位置的值交换，交换后key去中间，中间位置原来的值去最左边。此时，key的左边都是它路上经过的位置，这些位置的值已经在之前交换中满足了小于key的条件。唯一可能出问题的就是“中间位置的值”，它将成为新的最左边元素，继续留在key的左边。所以这个值必须小于key，才不破坏“左边小于key”的结构。

怎么保证相遇位置的值小于key？让j先走。j的任务是找小，它会一路从右往左找比key小的值，最后无论是j停下还是i撞上j，相遇位置都在j停下的位置，或者j还在某个比key小的位置附近。因为j每次只有在找到比key小的值时才会停下来，它停的地方天然就比key小。而i先走呢？i的任务是找大，它可能停在一个比key大的位置。如果j接着也找到一个比key小的位置，两者交换，那么i原先那个“大值”会被换走，位置又变回小值，看似没问题。

真正的坑在于“相遇”。如果i先走，走到一个比key大的位置停下，此时j也追过来相遇在这个位置，或者i在左边某个位置停下而j没有走到更小值就相遇了——这时候相遇位置的值有可能比key大，最后交换后这个大值会被换到key的左边，升序分区被破坏。这就是为什么“先移动哪根指针”不能乱来的原因。

我在推演过程中犯过这个错误，结论就是：key在左边时，必须先从j走，因为j找小，它走过的路能保证“最后停下的位置比key小”，这个位置才是安全的交换点。key取右边时反推，让i先走，因为i找大，它停下的位置比key大，交换后这个值会去右边，不破坏“右边大于key”的结构。

这个细节也被称为“保证相遇位置与key交换后的方向正确性”。我自己的记忆口诀是：谁最后交换key，就让能“保证交换安全”的那根针先出发。

3.2 等于基准值时，用什么判断条件

分区循环里最常出现的死循环问题就是边界判断条件写错。典型的一段伪代码是外层while (i < j)，内层两个while：一个while (i < j && a[i] <= key) i++;，另一个while (i < j && a[j] >= key) j--;。

可能有人觉得写<=和>=没毛病，相等值跳过去就行。但实际上对于重复值较多的数组，这种写法很容易导致死循环，或者频繁交换相同值的尴尬局面。

举个极端例子：[2, 2, 2, 2, 2]，key取2。如果内层用a[i] <= key，i会一路往右走；用a[j] >= key，j会一路往左走，两者相遇于中间某处，然后交换key和中间位置的值，看起来没事。但如果你的内层while写成了a[i] < key和a[j] > key，那就完全不同了：i会在第一个等于2的位置停下，j也在最右边等于2的位置停下，然后交换同一个值，但i和j并没有越过这个位置，外层while因为i<j仍然成立，之后继续走，i可能又停在这个2上，j又停在这个2上，交换来交换去都不动地方，直接陷入死循环。

实测下来最稳的做法是：内层循环用严格的<和>，不加等号。也就是写成while (i < j && a[i] < key) i++;和while (i < j && a[j] > key) j--;。这样等于key的值会留在原地，被两侧的交换动作逐步推向中间某个区域。虽然它可能在交换过程中左右横跳几次，但整体分区不会死循环。

如果用加等号的版本，需要额外注意循环终止条件，否则重复值场景必踩坑。我见过很多快速排序的报错现场，一跑大数据就卡死，排查到最后都是这里的问题。

3.3 边界条件与死循环的排查方法

写快排最容易踩的还有边界条件。比如左区间端点越过右端点，出现无限递归；或者i和j在循环中一前一后交错，导致交换越界或逻辑反转。

我自己的排查顺序是：

• 第一步，检查外层while的循环条件：必须是i < j，绝对不能允许i等于j时还继续走，否则必然交错。
• 第二步，检查内层两个while里是否也带了i < j判断。很多人外层写了，内层忘了，结果i一路走过头，直接越界。
• 第三步，检查递归调用时区间是否收敛：如果是左闭右闭区间，递归左边是[left, keyIndex - 1]，右边是[keyIndex + 1, right]，注意中间的keyIndex要排除，否则可能无限递归。
• 第四步，检查基准值选的是最左还是最右，对应的“先走指针”是否配套。

还有一个隐藏的坑：如果数组只有两个元素，例如[5, 1]，key取5，从j先走，j找小，找到1停下；i从左走，走一步到1和i相遇，交换key和1，变成[1, 5]，结束。看起来很正常。但如果数组是[1, 5]，key取1，从j走，j找小，走到位置0，和i相遇，最后交换key和相遇位置的值——key和它自己交换，分区结束。这也是正常的。只是要注意keyIndex在递归时要防止变成负数，比如递归左边时如果keyIndex已经是0，左边区间[left, keyIndex - 1]就变成了[0, -1]，必须判断left >= right时直接返回，这也是快排递归最常见的边界判断。

4. 常见错误速查与我自己摸索出的避坑经验

4.1 常见错误对照表

我在学习和给A同学讲快排时，整理过一张问题速查表。每次分区结果不对，按表排查基本能快速定位。

这张表不是空泛的理论，而是我挨个踩出来的。尤其“内层while不带i<j条件”这一条，我印象最深，因为自己写过一版，测试时数组长度稍微大一点就报数组越界。原因很简单：i在找大的过程中如果一直没找到，它会直接越过右边界，根本停不下来。

4.2 两个快速判断指针方向的口诀

虽然我一直强调不要背口诀，但实际做题和写代码时，口诀确实能迅速检查方向是否正确。我自己用的判断流程是：

• 第一步，先确定当前目标是升序还是降序。升序就记住“左小右大”，降序就记住“左大右小”。
• 第二步，看key取最左还是最右。这决定了谁先走，key在左先从右走，key在右先从左走。
• 第三步，判断“负责与key交换相遇位置”的指针是谁的先驱。具体来说：key在左时，最后与key交换的是j停的位置，j负责找“最终应该回到左边”的那类值。升序时这个值是“小值”，所以j找小，那i就找大。降序时这个值是“大值”，所以j找大，那i就找小。
• 第四步，如果key在右，表现就刚好镜像：最后交换时去右边的是i位置的值，升序时i应该找大、j找小，降序时i找小、j找大。

把这几条慢慢消化掉，你就掌握了从分区目标反推指针方向的完整方法。我自己后来写快排，每次写完都会拿一组包含正负数和小数、带重复值的数组先验一遍分区结果，确认左边各值和key的大小关系再继续递归。这个习惯帮我省了很多调试时间。

4.3 手写推演比跑代码更有效

最后分享一个我学习排序算法时最受益的习惯：纸上推演。调试快排的时候，与其对着IDE的断点一步步看，不如拿一张纸，写上原始数组，在每一趟分区上方标注当前key、指针i、指针j的位置。交换一次就画一条线，最后在数组下方写出这一趟结束后的状态。

比如上面那个降序遍历，我第一次在纸上推演的时候，就发现了自己“以为理解”但实际没有理解的错误——我当时按升序的逻辑去推降序，结果分区出来完全不成立。后来在纸上反复推了三遍，才真正看清楚“j先找大”和交换key的那一步为什么要一起配合。

这种“手动模拟”对于理解递归类算法尤其重要。因为递归的执行顺序不是线性的，你很难通过大脑直接跟踪多层调用的状态。手动推单趟分区的每一步，等分区逻辑彻底内化了，再看递归就清晰很多。

我还建议给自己准备几组固定的测试数组，反复用不同方向、不同key位置去跑：一组完全升序、一组完全降序、一组全部相等、一组随机、一组只有两个元素。把这些都推一遍，帮助非常大。我自己就是靠这几组数据把快排的边界条件和指针方向彻底搞明白的。

实际写代码的时候，我习惯把分区逻辑单独抽成一个函数，返回值就是key归位后的下标。主函数只负责递归调用，根本不碰指针细节。这样分区函数可以在小数组上单独访问测试，出错了也不至于一头扎进递归里找bug。对小白来说，这个习惯越早养成越好。

最后想说一句：如果你也卡在“i找大、j找小”这个问题上很久，不要怀疑自己笨。这个细节真的很绕，因为它同时牵扯升降序目标、基准值位置、指针移动顺序三条线索。但只要抓住“分区是为了让key归位，归位后左右两边符合目标顺序”这一条主线，把每一步交换的意义落到“这个值换到这边是否合适”上，所有口诀和顺序都会变得自然而然。我自己从“背口诀就忘”到“随手能写对”，靠的就是这一层推理。建议你也拿张草稿纸，把升序和降序各推演一遍，推完你就再也不怕快排了。