c - 这种修改后的快速排序划分算法在所有情况下都与原始划分算法的功能相同吗？

Question

QuickSort 分区过程类中给出的代码有两个内部循环，其中一个空空的 body 。假设我们通过将增量/减量从测试循环体，并相应地修改索引的初始值。原分区程序和修改后的分区程序如下:

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。因为自上一次迭代以来没有任何变化，所以循环将经历相同的测试并执行相同的操作，这等于什么都没有。因此无限循环。