如果更多重复键,快速排序算法改进

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

本书有以上算法的以下文字.

当文件中存在重复键时,指针交叉是微妙的.我们可以通过在i <j时终止扫描来稍微改进分区过程,然后使用j而不是i-1来分隔第一个递归调用的左子文件的右端.让循环在这种情况下再次迭代是一种改进,因为,当扫描循环以j和i引用同一元素终止时,我们最终在其最终位置有两个元素:停止两次扫描的元素,因此,它必须等于分区元素和分区元素本身.这种变化可能是值得的,因为在这种特殊情况下,程序会留下一个记录,其密钥等于[r]中的分区键,

我的问题是

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

谢谢你的时间和帮助.

Answer 1

>>如果存在更多重复键,为什么上面的快速排序算法不能有效工作？

因为你的破条件变得效率低下:if(i >= j) break;
所以,当你从两面都进行扫描以i和j,那你休息的时候这是很可能我==Ĵ而不是让i超越过j.

什么不好的时候,我们打破可能可能发生i==j时,许多重复键存在？

当你i==j;从第一个while循环中断时,你必须有a[i] >= v来自第二个while循环,a[j] <=v 但是因为我们正在考虑'break'来:i==jso,a[i] = a[j] = v即a[i],与v你的pivot元素相同.

在这种情况下,您的最外层exch(a[i], a[r]);将简单地将透视值交换给自己.
因此,在你quicksort(a, i+1, r);对数组的右半部分进行的下一次递归调用中,你将最小元素放在最右端.(你的枢轴选择策略很简单,item v = a[r];)我们都知道QuickSort选择一个枢轴元素是不好的达到阵列的最小值或最大值.因此,您对右半部分的后续递归调用将是一个退化的调用.
这就是为什么作者建议不要为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;
}

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