c++ - 我不明白这个快速排序的实现

Question

我有一个用 C++ 编写的快速排序代码，它非常适合非唯一元素的数组。相信在座的很多人都知道，但是，谁懂呢？让我更好地解释自己。这是代码:

void quicksort(int a[], int first, int last){
    int i,j;
    int pivot;

    if((last -first + 1) <= 1) return;

    pivot = a[(first+last) / 2];
    i = first;
    j = last;

    while(i <= j){
        while(a[i] < pivot) i++;
        while(a[j] > pivot) j--;

        if(i <= j){
            //SWAP
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;

            i++;
            j--;
        }
    }

    quicksort(a, first, j);
    quicksort(a,i, last);
}

所以，除了 if 之外，我什么都懂。谁能从数学上告诉我，在两个内部 while 之后 i > j 的确切情况或一组情况是什么？我知道它的具体情况，但它们发生的数学(或确切)属性是什么？

对不起，糟糕的英语，谢谢。

PD:请忽略这种情况下的优化，或者选择枢轴和所有其他东西。

Answer 1

如果开始时，a[i] > pivot(所以 i 不变)并且 a[j] > pivot 所有 j 直到 a[j] = pivot，循环的下一次迭代将导致 a j < i 的情况。

为了说明...

取下面的数组:

int a[] = [10, 7, 2, 6, 3];

在第一次调用快速排序时，first 为 0，last 为 4(数组中的最后一个索引)，pivot 将为 a[2] = 2。在 while 循环的第一次迭代中，a[0] > 2，所以我没有改变。 a[4] > 2, j--, a[3] > 2, j--, a[2] = 2，现在我们命中 if 语句。 0 <= 2，所以我们交换 a[0] 和 a[2] 并执行 i++ 和 j--。

现在数组看起来像这样:

[2, 7, 10, 6, 3]

i = 1 和 j = 1.a[i] > 2，所以 i 没有改变。 a[j] > 2，所以 j--，j 现在为 0。a[j] 不大于 2(因为它是 2)，j 保持为 0。现在，我们有 i = 1 和 j = 0 , 或 i > j.

如果您注意到，2 处于“已排序”位置，不再需要移动。此外，枢轴是数组中的最小元素。希望能帮助您解决问题。