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

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

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

由于您的破坏条件是：它变得无效，

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

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