c++ - 如果有更多重复键，则快速排序算法改进

Question

我正在阅读 Robert Sedwick 算法和数据结构第 1-4 部分中的快速排序算法。

template <class item>

static void quicksort(item [] a, int l, int r)
{
    if(r <= l) return;
    int i = partition(a,l,r);
    quicksort(a, l, i-1);
    quicksort(a, i+1, r);
}

template <class item>
int partition(item a[], int l, int r)
{
    int i = l-1; j = r; item v = a[r];

    for(;;) {
        while( a[++i] < v );
        while( v < a[--j] ) 
            if( j == l ) 
                break;
        if( i >= j) 
            break;  // pointer crossing.
        exch(a[i], a[j]);
    }

    exch(a[i], a[r]);
    return i;
}

书中有以下关于上述算法的文字。

When duplicate keys are present in the file, the pointer crossing is subtle. we could improve the partitioning process slightly by terminating the scans when i < j, and then using j, rather than i-1, to delimit the right end of the left subfile for the first recursive call. Letting the loop iterate one more time in this case is an improvement, because, when ever the scanning loops terminate with j and i referring to the same element, we end up with two elements in their final positions: the element that stopped both scans, which must therefore be equal to the partitioning element, and the partitioning element itself. This change is probably worth making, because, in this particular case, the program leaves a record with a key equal to the partitioning key in a[r], and that makes the first partition in the call quick-sort(a, i+1, r) degenerate, because its right most key is its smallest.

我的问题是

1. 我们如何根据下面的描述修改上面的程序？我很难修改它以理解文本。
2. 如果存在更多重复键，为什么上述快速排序算法无法有效工作。
3. 如果存在更多重复键，上述修改如何改进？
4. 作者所说的“调用 quick-sort(a, i+1, r) 时的第一个分区退化，因为它最右边的键是它的最小键”是什么意思。 ？做什么 作者在这里指的是退化？

感谢您的宝贵时间和帮助。

Answer 1

>>如果存在更多重复键，为什么上述快速排序算法无法有效工作？

它变得低效，因为你的破坏条件是:if(i >= j) break;
因此，当您使用 i 从两面进行扫描时和 j ，很有可能你在 i == j 而不是让 i 时中断超越j .

当我们打破 i==j 时可能会发生什么坏当存在许多重复键时？

当你为 i==j; 休息时从第一个 while 循环开始，你一定有 a[i] >= v从第二个 while 循环 a[j] <=v但由于我们正在考虑“中断”:i==j所以，a[i] = a[j] = v即 a[i]与 v 相同，您的枢轴元素。

在这种情况下，你的最外层exch(a[i], a[r]);将简单地将枢轴值交换给自己。
因此，在您的下一个递归调用中 quicksort(a, i+1, r);对于数组的右半部分，您将在最右端放置最小元素。(您的枢轴选择策略很简单，item v = a[r];)我们都知道快速排序选择一个等于最小值的枢轴元素是不好的或数组的最大值。因此，您随后对右半部分的递归调用将是一个退化。
这就是为什么作者建议不要为 i==j 中断，而是在发生之前捕获它们。

>>作者这里的退化是什么意思？

此处的退化意味着递归树变得倾斜，即后续问题的生成规模几乎不相等。 你正在划分一个大小的问题 N变成类似大小的问题N-1和 1而不是更平衡的东西，比如把它分成大小的问题 N/2和 N/2 .

>>我们如何根据下面的描述修改上面的程序？

我们可以像下面这样实现它:

int partition(int A[], int l, int r){
        int i=l-1, j=r, v = A[r];
        for(;;){
                while(A[++i] < v);
                while(A[--j] > v)
                        if(j == l)
                                break;
                if(i>=j)
                        break;
                swap(A[i], A[j]);
        }
        if(i == j){// case when we stopped at the pivot element.
                j = j+1;//backtrack j 1 step.
                if(j <= r)
                    swap(A[j], A[r]);
                return j;// partition the subsequent problems around j now.
        }
        swap(A[i], A[r]);
        return i;
}

>>如果存在更多重复键，上述修改如何改进？
它通过让您不生成退化案例的明显场景来提高性能。