Java快速排序partition函数中第二次swap的必要性解析

先明确这个Partition函数的核心目标：选左侧第一个元素作为基准值（pivot），最终要把pivot放到数组中的正确位置——也就是pivot左边的元素都≤它，右边的元素都＞它，这样后续才能递归排序左右两部分。

咱们拆解循环结束后的状态：
当i > j时，循环停止。此时：

• 所有下标≤j的元素，都是≤pivot的；
• 所有下标≥i的元素，都是＞pivot的。

但此时pivot还待在初始的links（左边界）位置，这个位置的元素是pivot，但它不一定在正确的分界点上——比如看这个例子：

int[] array = {3,1,2,4,5};

pivot是3，循环结束后j=2（对应元素2，是最后一个≤3的元素），如果不执行swap(array, links, j)，pivot还在位置0，此时右边的元素1、2都是≤3的，完全不符合Partition的要求，后续递归排序肯定会出错。

执行第二次交换后，pivot被换到j的位置，数组变成{2,1,3,4,5}，此时3左边的元素都≤它，右边都＞它，完美达成Partition的目标，接下来递归处理[0,1]和[3,4]即可。

你觉得有序数组里不需要这次交换，是因为特殊情况：当数组本身有序时，循环结束后j会等于links（比如数组{1,2,3,4,5}，循环结束后j=0），交换同一个位置相当于没操作，所以看起来多余，但这只是个例。对于大部分无序的情况，这次交换是必须的，它是把pivot归位的关键步骤，没有它，Partition的结果就不满足快速排序的要求。

内容的提问来源于stack exchange，提问作者user10597289