为何替换Mark Allen Weiss版快速排序分区代码会引发无限循环？

在Mark Allen Weiss所著书籍的快速排序实现中，Median函数用于选取数组左、右、中间位置元素的中位数作为基准值（pivot）。当原分区逻辑被替换为指定代码后，一旦出现a[i] = a[j] = pivot的情况，就会触发无限循环，具体原因如下：

相关代码 #

Median函数 #

template<typename Comparable>
const Comparable Median(vector<Comparable> & array, int left, int right)
{
    int center = (left + right) / 2;
    if (array[left] > array[right])
        swap(array[left], array[right]);
    if (array[center] > array[right])
        swap(array[center], array[right]);
    if (array[left] > array[center])
        swap(array[left], array[center]);
    swap(array[center], array[right - 1]);

    return array[right - 1];
}

原快速排序分区代码 #

int i = left; int j = right - 1;
while (i < j)
{
    while (array[++i] < pivot);
    while (array[--j] > pivot);
    swap(array[i], array[j]);
}

替换后的分区代码 #

int i = left + 1, j = right - 2;
for (; ; )
{
    while (a[i] < pivot) i++;
    while (pivot < a[j]) j--;
    if (i < j)
        std::swap(a[i], a[j]);
    else
        break;
}

无限循环的核心原因 #

替换后的分区逻辑存在指针停滞的问题：

1. 当a[i] = pivot时，while (a[i] < pivot)的条件不成立，i会停止移动；同理，当a[j] = pivot时，while (pivot < a[j])的条件不成立，j也会停止移动。
2. 此时如果i < j，代码会执行swap(a[i], a[j])，但交换的两个元素都是pivot，交换后a[i]和a[j]的值没有变化。
3. 进入下一轮循环时，i和j的位置完全没变，两个while循环依然不会触发指针移动，再次执行swap，如此反复就陷入了无限循环。

对比原分区代码的逻辑：
原代码的循环是while (array[++i] < pivot)——先自增i再判断，即使遇到等于pivot的元素，i也已经完成了自增；同理while (array[--j] > pivot)会先自减j再判断。这种设计保证了指针不会停在原地，即使遇到等于pivot的元素，也会强制移动指针，避免了死循环的发生。

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