如果有更多重复的键，则可以快速改进排序算法

小编典典

如果有更多重复的键，则可以快速改进排序算法

algorithm

我正在阅读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指向同一元素终止时，我们最终将在其最终位置出现两个元素：停止两次扫描的元素，因此，它必须等于分区元素以及分区元素本身。这种更改可能值得进行，因为在这种特殊情况下，程序会留下一个键，该键的键等于a
[r]中的分区键，

我的问题是

我们如何用下面的描述修改上面的程序？我很难对其进行修改以理解文本。
如果存在更多重复的键，为什么上述快速排序算法无法有效工作。
如果存在更多的重复密钥，上述修改如何改进？
作者的意思是“他在电话快速排序（a，i + 1，r）中的第一个分区退化了，因为它最右边的键是它的最小键。” ？作者在这里退化是什么意思？

感谢您的时间和帮助。

阅读 196

2020-07-28

共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);数组的Right-
half时，您将有最少的元素位于最右边。（您的数据透视选择策略很简单，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;
}

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

2020-07-28