K＆R快速排序代碼

Question

我檢查了K & R書中的快速排序代碼，2小時後我仍然無法理解第一個交換（swap(a, left, (left+right)/2);）實現的效果。我試圖刪除它，排序仍然有效。 有人可以解釋嗎？這是一個性能問題？如果是這樣，爲什麼？這個動作對我來說似乎是隨機的（就是說，在一些數字上它會提高性能，而在某些情況下則不會）。

謝謝。

void qsort(int a[], int left, int right) 
{ 
    int i, last; 

    if (left >= right) 
     return; 

    swap(a, left, (left+right)/2); 

    last = left; 
    for (i = left + 1; i <= right; i++) 
     if(a[i] < a[left]) 
      swap(a, ++last, i); 

    swap(a, left, last); 
    qsort(a, left, last-1); 
    qsort(a, last+1, right); 
} 

Answer 1

它把樞軸元件到所述子陣列的非常第一位置。

然後它繼續圍繞樞軸分區子陣列，以便在分區完成後，子陣列看起來像這樣：[pivot, [elements < pivot], [elements >= pivot]]。

之後，主軸簡單地放在適當的空間，所以子陣列看起來像這樣：[[elements < pivot], pivot, [elements >= pivot]]。

然後，遞歸調用在兩個子子數組上進行。

無論選擇哪個元素作爲關鍵點，快速排序總能正常工作。如果你選擇中位數元素，那麼時間複雜度將是線性的（O（nlogn））。但是，如果您選擇最大的元素作爲支點，那麼性能將降至二次（O（n^2））。因此，本質上，樞軸選擇是Quick-Sort性能的關鍵，但它會起作用（當我說工作時，我的意思是最終會得到一個有序數組）。

Answer 2

K & R實現爲中心選擇中間索引（即(left+right)/2）。取消這一行代替使用最左邊的元素。實現仍然有效，但是當數組已經排序後，性能會下降。

Wikipedia article說明這一點：

在快速排序的非常早期版本中，分區的最左邊的元素往往會被選擇作爲樞轉元件。不幸的是，這會導致已排序數組的最壞情況行爲，這是一種相當常見的用例。這個問題很容易解決，方法是選擇一個隨機索引作爲主鍵，選擇分區的中間索引或者（特別是對於更長的分區），選擇分區的第一個，中間和最後一個元素的中位數（如塞奇威克）。