9

我正在阅读 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] 中的分区键，

我的问题是

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

感谢您的时间和帮助。

4

1 回答 1

6

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

它变得低效，因为您的中断条件是：因此，当您使用andif(i >= j) break;
从两侧扫描时，很有可能您在i == j时中断而不是让超过。当我们在存在许多重复键时中断可能会发生 什么坏事？ijij

i==j

当您i==j;从第一个 while 循环中中断 for 时，您必须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];）并且我们都知道快速排序选择一个枢轴元素是不好的等于数组的最小值或最大值。因此，您随后对 right-half 的递归调用将是退化的。
这就是为什么作者建议不要因为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;
}

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

于 2012-11-12T09:25:14.813 回答