使用三位羅伯特塞德威克中位數的快速排序改進

Question

羅伯特塞迪威克算法書中快速排序部分的文字。

通過從數組的左邊，中間和右邊選擇三個元素，我們可以將標記合併到這個方案中。對三個元素進行排序，然後在中間與a[r-1]進行交換，然後在a[l+1],...,a[r-2]上運行分區算法。這種改進稱爲三種方法的中位數。

三種方法的中位數有助於以三種方式快速排序。

1. 這使最壞的情況在任何實際的排序中都不太可能發生。對於需要執行O(N^2)時間的排序，所檢查的三個元素中的兩個元素必須位於文件中最大元素或最小元素之間，並且此事件必須始終貫穿大部分分區。

2. 它消除了用於分區的標記鍵的必要性，因爲此功能由分區之前檢查的三個元素之一提供。

3. 它將算法的總平均運行時間減少了大約5％。

   template <class Item> 
   void exch(Item &A, Item &B) 
        { Item t = A; A = B; B = t; } 
   
   template <class Item> 
   void compexch(Item &A, Item &B) 
        { if (B < A) exch(A, B); } 
   
   static const int M = 10; 
   template <class Item> 
   void quicksort(Item a[], int l, int r) 
       { 
       if (r-l <= M) return; 
       exch(a[(l+r)/2], a[r-1]); // line 1 
       compexch(a[l], a[r-1]); // line 2. 
       compexch(a[l], a[r]);  // line 3. 
       compexch(a[r-1], a[r]); // line 4. 
       int i = partition(a, l+1, r-1); 
       quicksort(a, l, i-1); 
       quicksort(a, i+1, r); 
       } 
   
   template <class Item> 
   void hybridsort(Item a[], int l, int r) 
       { quicksort(a, l, r); insertion(a, l, r); } 
   

我上面的文字問題，可以在任何一個簡單的例子來解釋

1. 什麼是筆者的「最壞的情況下更不可能在任何實際的排序發生的意思。對於按照N平方時間排序，所檢查的三個要素中的兩個必須是最大的「？

2. 作者的意思是「它消除了對分區進行定位密鑰的必要性」？

3. 在上面的程序中，我們在上面的代碼中評論的第1,2,3和4行中實現了什麼？

感謝您的時間和幫助！

Answer 1

快速排序算法的優點是將數據分成兩半，然後對每一半進行排序併合並結果。這種行爲使得它具有O（N log N）複雜性。然而，這是基於這樣一個事實，即當您將這些數據分成一半時，實際上將其分成兩半。然而，這並非總是如此。你不只是分割數組，你將分成兩部分，但將每個元素與分區元素進行比較（比如P）。如果一個元素小於或等於P，那麼它進入左邊的子數組，否則就進入右邊的子數組。所以子數組的大小很大程度上取決於分區元素。如果P等於數組中的最大值或最小值，則其中一個子陣列將爲空，並且快速排序將不會從「分段階段」中獲得任何結果。如果這種情況每次都會持續，那麼算法的運行時間將變爲O（N^2）

「三個中值」方法通過將分區元素設置爲中值而防止分區元素成爲陣列的最大或最小元素三個選定元素的元素。

代碼中的四行有效地對三個元素進行排序，並選擇中間的一個作爲新分區。如果你打算比較三個要素來確定中位數，你可以同時對它們進行排序。