快速排序的 partition 函数中，第二次 swap（即 swap(array, links, j)）是关键步骤：它将基准元素从起始位置移动到其在排序后数组中的正确位置，确保左子数组全 ≤ 基准、右子数组全 > 基准，从而为递归划分提供正确边界。
快速排序的 partition 函数中，第二次 swap（即 swap(array, links, j)）是关键步骤：它将基准元素从起始位置移动到其在排序后数组中的正确位置，确保左子数组全 ≤ 基准、右子数组全 > 基准，从而为递归划分提供正确边界。
在您实现的 Lomuto 风格分区逻辑中，基准元素（pivot）始终取自子数组最左侧：pivotelement = array[links]。整个 while 循环的目标是重新排列 [links, rechts] 范围内的元素，使得：
- 所有
≤ pivotelement的元素位于某个连续前缀中； - 所有
> pivotelement的元素位于后续后缀中； - 但此时基准元素仍“卡”在索引
links处——它尚未被安置到最终有序位置。
循环结束时，变量 i 和 j 满足 i > j，且根据循环条件和分支逻辑可推知：
✅ array[links...j] 中所有元素都 ≤ pivotelement（注意：j 是该区域的右边界索引）；
✅ array[j+1...rechts] 中所有元素都 > pivotelement；
❌ 但 array[links]（即 pivot 本身）仍处于原位，可能破坏上述结构——例如，若 array[links] 是最大值，它本应落在 j 位置右侧，却滞留在左侧起点。
因此，swap(array, links, j) 的作用是：将 pivot 元素“就位”到索引 j 处，使其恰好成为左半区的最后一个元素。此时：
- 子数组
[links, j-1]全 ≤ pivot（因array[j]现为 pivot，且原array[links...j]≤ pivot）； - 子数组
[j+1, rechts]全 > pivot； - 返回
j即表示：pivot 的最终索引为j，左递归处理[links, j-1]，右递归处理[j+1, rechts]。
来看一个简明示例（省略循环细节，聚焦交换）：
// 初始: [7, 2, 9, 1, 5], links=0, rechts=4, pivot=7 // 循环结束后（i=3, j=2）: [7, 2, 5, 1, 9] → 此时 array[0..2] = [7,2,5]，但 7 不应在此！ // 执行 swap(array, 0, 2): [5, 2, 7, 1, 9] // 现在：左半区 [5,2]（索引0–1）≤ 7，右半区 [1,9]（索引3–4）> 7？不对——1 <p>⚠️ 注意：上述推演说明仅靠循环无法保证 <code>array[links...j]</code> 严格 ≤ pivot —— 因为 <code>array[links]</code> 自身未参与比较。<strong>真正成立的是：循环终止时，<code>j</code> 是首个满足 <code>array[j] ≤ pivot</code> 且其右侧（<code>j+1</code> 起）全 <code>> pivot</code> 的位置</strong>。而 <code>array[links]</code> 作为 pivot，必须被移走，才能让 <code>j</code> 成为 pivot 的归属点。</p><p>修正后的正确理解（以您的代码为例）：<br> 循环本质是在寻找 pivot 的“目标槽位”。当 <code>i</code> 和 <code>j</code> 交错时，<code>j</code> 恰好停在<strong>最后一个 ≤ pivot 的元素索引上</strong>（即使该元素不是 pivot）。于是 <code>swap(array, links, j)</code> 将 pivot 与该元素互换，使 pivot 落入最终位置，同时保证：</p>
-
array[links]到array[j-1]：≤ pivot（因原array[j]≤ pivot，且循环中所有被保留在左部的元素均满足此条件）； -
array[j+1]到array[rechts]：> pivot（由j--的退出条件保证）。
这也是为何对已排序数组（如 [1,2,3,4,5]）看似“不需要”第二次交换——实际上它仍执行，但 j 恰好等于 links，交换自身无变化，逻辑依然自洽。
✅ 总结关键点：
- 第一次交换（
swap(array,i,j)）用于内部调整：将左侧过大元素与右侧过小元素对调，逼近分区边界； - 第二次交换（
swap(array,links,j)）用于基准就位：将 pivot 放入其排序后的位置j，这是划分左右子问题的必要锚点； - 若省略第二次交换，pivot 会滞留在左端，导致递归调用时区间错乱（如左子数组包含 pivot，右子数组可能遗漏或重复），算法失效。
因此，无论输入是否有序，该 swap 都是分区逻辑完整性和正确性的基石，不可省略。
