如果有更多重复密钥，快速排序算法的改进

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;
}

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

当文件中存在重复键时，指针交叉很微妙。我们可以稍微改进分区过程，当我

我的问题是

1. 我们如何用下面的描述修改上面的程序？我在修改它以理解文本方面有困难。
2. 为什么上面的快速排序算法不能有效地工作，如果存在更多的重复密钥。
3. 如果存在更多的复制键，上述修改如何改进？
4. 作者所说的第一个分区在调用快速排序（a， i 1， r）中退化是什么意思，因为它的最右键是它的最小键。作者这里所说的堕落是什么意思？

谢谢你的时间和帮助。

Answer 1

当你为i==j而中断时 从第一个while循环开始，您必须有a[i]

在这种情况下，最外层的exch（a[i]，a[r]） 只需将枢轴值交换给自身
因此，在下一个递归调用快速排序（a，i 1，r）对于数组的右半部分，最小元素位于最右边。（您的透视选择策略很简单，项v=a[r]；）我们都知道，快速排序选择数组中最小或最大的透视元素是不好的。因此，对右半部分的后续递归调用将是退化调用<这就是为什么作者建议不要因为i==j而中断，而是在这之前抓住它们

这里的退化意味着，递归树变得倾斜，即随后的问题没有产生几乎相等的大小。你把一个大小的问题分成大小的问题，比如N-1和1的问题，而不是更平衡的问题，比如把它分成大小的问题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;
}