快速排序算法改進，如果更多的重複鍵

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

書上面的算法有以下文本。

當文件中存在重複鍵時，指針交叉點是 細微。我們可以稍微改進分區過程 終止掃描，然後使用j而不是i-1, 爲第一次遞歸調用 定界左側子文件的右端。在這種情況下讓循環迭代一次就是 的改進，因爲當掃描循環以j 終止並且我指向相同的元素時，我們最終得到兩個元素： 它們的最終位置：停止的元素這兩個掃描，因此必須是 等於分區元素，並且分區 元素本身。這種改變可能是值得的，因爲在這種情況下，程序會在[r]中留下一個關鍵字等於 分區鍵的記錄，並使 中的第一個分區調用快速排序（a ，i + 1，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，但由於我們正在考慮爲一個「休息」：i==j所以，a[i] = a[j] = v即a[i]與v相同，您的主要元素。

在這種情況下，您最外面的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; 
} 

>>怎麼以上修改完善，如果更多的重複鍵出現的？
它通過讓您不生成退化情況的明顯場景來提高性能。