快速排序（QuickSort）的核心思想是分治法。它的灵魂在于 partition（分区）函数。

我将通过拆解你提供的代码，配合图解，专门通过边界条件来帮你把逻辑理顺。

1. 宏观理解 partition 的目的

partition 函数要做的事情只有一件： 选定一个基准值（Pivot），把比它小的都扔到左边，比它大的都扔到右边。

至于左右两边内部是否有序，它不管。最后它返回基准值应该所在的正确索引位置。

2. 关键变量的含义

在你的代码中：

• pivot = arr[low]：我们默认把数组最左边的数当作基准值。
• left = low + 1：左探针。因为 arr[low] 是基准值，所以我们要从它后面一个开始检查。
• right = high：右探针。从数组最末尾开始检查。

3. 核心循环边界详解

这是你最困惑的地方，我们逐行拆解：

A. 最外层循环 while (left <= right)

为什么要带 = (等于号)？ 这是为了保证所有元素都被检查过，并且让 left 和 right 彻底交错开。

• 当 left == right 时，说明还有一个元素（就是中间那个）没有被归类。我们需要继续进入循环，判断这最后一个元素是比 Pivot 大还是小。
• 只有当 left > right 时（即 right 跑到了 left 的左边），循环才结束。此时，right 指向的是左边区域（小于等于Pivot）的最后一个元素，而 left 指向的是右边区域（大于Pivot）的第一个元素。

B. 左探针循环 while (left <= right && arr[left] <= pivot) left++

含义： “只要 left 还没跑到 right 右边，且当前数字小于等于基准值，我就继续往右走。” 目的： 它的任务是寻找比 Pivot 大的刺头。如果当前数字很乖（比 Pivot 小），它就忽略，继续往右移，直到找到一个比 Pivot 大的数停下来，或者撞到墙（left > right）。

• 为什么要 left <= right？ 防止数组越界。如果 pivot 是数组里最大的数，left 会一直加一直加，如果没有这个限制，它会跑出数组边界。

C. 右探针循环 while (left <= right && arr[right] >= pivot) right--

含义： “只要 right 还没跑到 left 左边，且当前数字大于等于基准值，我就继续往左走。” 目的： 它的任务是寻找比 Pivot 小的刺头。如果当前数字比 Pivot 大，它就忽略，继续左移，直到找到一个比 Pivot 小的数停下来。

D. 交换 if (left < right)

含义：

• 此时 left 停在一个大数上。
• 此时 right 停在一个小数上。
• 如果 left 还在 right 左边，说明这两个人站错队了！
• Action： 交换它俩的位置。大数去右边，小数去左边。

4. 为什么最后要 swap(arr, low, right)？

这是理解快排最关键的一步。

当大循环 while (left <= right) 结束时，由于 left 和 right 已经交错（Crossed），状态如下：

• right 的位置：停在了小于等于 Pivot 的最后一个元素上（属于左半区）。
• left 的位置：停在了大于 Pivot 的第一个元素上（属于右半区）。
• low 的位置：仍然是我们的 Pivot（基准值）。

因为 Pivot 本身属于“中间值”，它应该位于“小数区”和“大数区”之间。 而 right 指向的是“小数区”的边界（最右侧）。 所以，我们将 Pivot (arr[low]) 与 arr[right] 交换。

这样一来：

• Pivot 就坐到了 right 这个位置。
• right 左边的都比 Pivot 小。
• right 右边的都比 Pivot 大。
• 函数返回 right，告诉 quickSort：“这里切一刀，下次排左边和右边”。

5. 举个例子模拟（视觉化）

假设数组：[6, 1, 2, 7, 9, 3, 4, 5, 10, 8]low = 0, high = 9pivot = 6 (对应 arr[0]) left = 1 (指向 1), right = 9 (指向 8)

第一轮大循环：

1. Left 走：
   • 1 <= 6? 是，left++ (变成2，指向2)
   • 2 <= 6? 是，left++ (变成3，指向7)
   • 7 <= 6? 否，Left 停在 7。
2. Right 走：
   • 8 >= 6? 是，right-- (变成8，指向10)
   • 10 >= 6? 是，right-- (变成7，指向5)
   • 5 >= 6? 否，Right 停在 5。
3. Swap判断： left(3) < right(7)，交换 7 和 5。
   • 数组变：[6, 1, 2, 5, 9, 3, 4, 7, 10, 8]

第二轮大循环：

1. Left 走： 从 9 开始（之前 left 在索引 3，刚换成了 5，现在继续走会发现 5<=6，走到索引 4）
   • 9 <= 6? 否，Left 停在 9。
2. Right 走： 从 4 开始
   • 4 >= 6? 否，Right 停在 4。
3. Swap判断： left(4) < right(6)，交换 9 和 4。
   • 数组变：[6, 1, 2, 5, 4, 3, 9, 7, 10, 8]

第三轮大循环：

1. Left 走： 指向 9
   • 9 <= 6? 否，Left 停在 9 (索引 6)。
2. Right 走： 指向 3
   • 3 >= 6? 否，Right 停在 3 (索引 5)。
3. Swap判断： left(6) < right(5) 吗？ 不！left > right 了！
   • 不交换。
   • 退出大循环 while (left <= right)。

最后一步： 此时状态：

• right 指向 3 (索引 5)，这是小数区的最后一个。
• pivot 在开头 (索引 0)，值为 6。
• 执行 swap(arr, low, right) -> 交换 6 和 3。

数组最终形态： [3, 1, 2, 5, 4, 6, 9, 7, 10, 8] 注意看数字 6： 左边 3,1,2,5,4 都比 6 小。 右边 9,7,10,8 都比 6 大。 Partition 完成，返回索引 5。

总结

• left <= right：保证两者完全错开，right 能准确停在小数区的边界。
• arr[left] <= pivot：left 负责跳过小数，找大数。
• arr[right] >= pivot：right 负责跳过大数，找小数。
• swap(low, right)：因为 right 最终指向的是比 Pivot 小的那个数（或者就是 Pivot 自己），所以把 Pivot 换过去是安全的。

“right 最终指向小数区的最后一个，left 最终指向大数区的第一个” 这个结论在循环结束后依然是绝对成立的。