C语言 快速排序中修改后的分区算法是否在所有情况下都与原始算法相同

Question

类

中给出的用于快速排序分区过程的代码有两个内部循环，带有空身。假设我们通过从测试循环主体，并相应地修改索引的初始值。原始和修改后的分区过程如下：

int partition( A[], int l, int r )
{
    int pivot = A[l];
    int i = l, j = r+1;
    while(i < j)
    {
        while (A[--j] > pivot);
        while (A[++i] < pivot);
        if (i < j) swap (A[i], A[j]);
    }
    swap(A[l], A[j]);
    return j;
}
int partition( A[], int l, int r )
{
    int pivot = A[l];
    int i = l+1, j = r;
    while (i < j)
    {
         while (A[j] > pivot) j--;
         while (A[i] < pivot) i++;
         if (i < j) swap(A[i], A[j]);
    }
    swap(A[l], A[j])
    return j;
}

修改后的分区过程是否在所有情况下都能正常工作？（忽略当枢轴是最大元素时，我跑掉数组的故障）。提示：考虑什么当当前子数组包含至少两个与枢轴相等的其他键时发生。

Answer 1

当子数组包含至少两个与透视相等的其他值时，修改后的分区过程将进入无限循环。

让我们考虑一个案例，我们有：

    int A[] = { 3, 3, 1, 3 };

我们称之为：

    partition(A, 0, 3);

在外部while循环的第一次迭代中，i为 1，j为 3：

3 3 1 3
  ^   ^  
  i   j

考虑第一个测试：

         while (A[j] > pivot) j--;

3

大于 3 是不正确的，因此j不会递减。

现在第二个测试：

         while (A[i] < pivot) i++;

同样，3

小于 3 也不是真的，因此 i 不会递增。

当A[i]与A[j]交换时，数组不会改变，因为i和j的值相同。

循环开始新的迭代，因为i仍然小于 j 。因为自上一次迭代以来没有任何变化，所以循环将经历相同的测试并做同样的事情，这相当于什么都没有。因此无限循环。