Quicksort優於堆排序

Question

堆排序的最壞情況複雜度爲O(nlogn)，而Quicksort有O(n^2)。 但是，經驗證據表明快速排序是優越的。這是爲什麼？

Answer 1

其中一個主要因素是快速排序更好參考地點 - 下一次要訪問的內容通常與您剛剛查看的內容密切相關。相比之下，heapsort跳躍明顯更多。由於相互靠近的東西可能會一起緩存，快速排序往往會更快。

但是，quicksort的最糟糕的情況表現明顯比heapsort差。由於某些關鍵應用程序需要保證速度性能，所以heapsort是這種情況的正確途徑。

Answer 2

這裏有一對夫婦解釋：

http://www.cs.auckland.ac.nz/software/AlgAnim/qsort3.html

http://users.aims.ac.za/~mackay/sorting/sorting.html

從本質上講，即使對於快速排序的最壞情況是O（n^2）其平均將有更好的表現。 :-)

Answer 3

平均情況下的複雜度，以及您可以採取簡單的步驟來最小化Quicksort中最壞情況複雜度風險的事實（例如，選擇樞軸作爲三個元素的中值而不是單個選定的位置） 。

Answer 4

big-O表示法意味着排序n個項目所需的時間由函數c*n*log(n)限定，其中c是某些未指定的常數因子。 quicksort和heapsort的常數c應該是相同的。所以真正的問題是：你爲什麼期望它們同樣快？

Quicksort實際上一直比heapsort要快一些，但是最近的區別變得更大了，因爲如前所述，存儲器訪問的局部性對於執行速度變得如此重要。

Answer 5

heapsort是O（N log N）保證，什麼比Quicksort中的最壞情況好得多。 Heapsort不需要更多的內存來存儲另一個數組，以根據Mergesort的需要放置有序數據。那麼爲什麼商業應用程序堅持使用Quicksort？ Quicksort與其他實現有什麼特別之處？

我已經測試過我自己的算法，我已經看到Quicksort確實有些特別的東西。它運行速度快，比堆和合並算法快得多。

Quicksort的祕訣是：它幾乎不會做不必要的元素交換。交換非常耗時。

使用Heapsort，即使您的所有數據都已經排序，您將要交換100％的元素來排列數組。

隨着Mergesort，情況更糟。即使已經訂購了數據，您也會在另一個數組中寫入100％的元素並將其寫回原始數據。

使用Quicksort，您不會交換已經訂購的東西。如果你的數據是完全有序的，你幾乎沒有交換！儘管最糟糕的情況還有很多值得關注的地方，但是對數據透視的選擇有一點改進，除了獲取數組的第一個或最後一個元素之外，可以避免它。如果從第一個元素，最後一個元素和中間元素之間的中間元素獲得一個支點，則避免最壞情況是很不恰當的。

Quicksort的優越性不是最壞的情況，而是最好的情況！在最好的情況下，你做相同數量的比較，好的，但你幾乎沒有交換。在平均情況下，您可以交換部分元素，但不是所有元素，例如Heapsort和Mergesort。這就是Quicksort最好的時機。交換少，速度快。

在我的計算機上運行在釋放模式下的C＃中的實現，在中間透視下以3秒擊敗Array.Sort，在改進透視下以2秒擊敗Array.Sort（是的，有一個額外開銷以獲得良好的支點）。

static void Main(string[] args) 
{ 
    int[] arrToSort = new int[100000000]; 
    var r = new Random(); 
    for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length); 

    Console.WriteLine("Press q to quick sort, s to Array.Sort"); 
    while (true) 
    { 
     var k = Console.ReadKey(true); 
     if (k.KeyChar == 'q') 
     { 
      // quick sort 
      Console.WriteLine("Beg quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff")); 
      QuickSort(arrToSort, 0, arrToSort.Length - 1); 
      Console.WriteLine("End quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff")); 
      for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length); 
     } 
     else if (k.KeyChar == 's') 
     { 
      Console.WriteLine("Beg Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff")); 
      Array.Sort(arrToSort); 
      Console.WriteLine("End Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff")); 
      for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length); 
     } 
    } 
} 

static public void QuickSort(int[] arr, int left, int right) 
{ 
    int begin = left 
     , end = right 
     , pivot 
     // get middle element pivot 
     //= arr[(left + right)/2] 
     ; 

    //improved pivot 
    int middle = (left + right)/2; 
    int 
     LM = arr[left].CompareTo(arr[middle]) 
     , MR = arr[middle].CompareTo(arr[right]) 
     , LR = arr[left].CompareTo(arr[right]) 
     ; 
    if (-1 * LM == LR) 
     pivot = arr[left]; 
    else 
     if (MR == -1 * LR) 
      pivot = arr[right]; 
     else 
      pivot = arr[middle]; 
    do 
    { 
     while (arr[left] < pivot) left++; 
     while (arr[right] > pivot) right--; 

     if(left <= right) 
     { 
      int temp = arr[right]; 
      arr[right] = arr[left]; 
      arr[left] = temp; 

      left++; 
      right--; 
     } 
    } while (left <= right); 

    if (left < end) QuickSort(arr, left, end); 
    if (begin < right) QuickSort(arr, begin, right); 
}