爲什麼當有很多重複元素時快速排序效率低下？

Question

當我排序有許多重複元素的數據時，快速排序算法效率低下。任何人都可以解釋爲什麼？
這裏是我的快速排序代碼：

int partition(int arr[],int low,int high) 
{ 
    int i = low + 1; 
    int j = high; 
    int tmp = arr[low]; 
    while(1) 
    { 
     while(j != low && arr[j] > tmp) --j; //from right to left 
     while(i != high && arr[i] <= tmp) ++i; //from left to right 
     if(i < j) 
     { 
      int t = arr[j]; 
      arr[j] = arr[i]; 
      arr[i] = t; 
     } 
     else 
      break; 
    } 
    return j; 
} 

void QuickSort(int arr[],int low,int high) 
{ 
    if(low < high) 
    { 
     int j = partition(arr,low,high); 
     int t = arr[j]; 
     arr[j] = arr[low]; 
     arr[low] = t; 
     if(low < j) 
      QuickSort(arr,low,j-1); 
     if(high > j) 
      QuickSort(arr,j+1,high); 
    } 
} 

Answer 1

我的心理調試技巧告訴我，不僅確實你的投入有很多重複，但重複的元素是連續，這使得輸入大多排序下手。一個大多數排序的容器是快速排序的最差情況，性能降低到O(n^2)。

對於大多數有序的輸入，像堆排序和合並排序等其他排序將提供更好的性能，因爲他們的最壞情況是他們的平均情況下更高的常數。

Answer 2

以下示例quicksort代碼與問題中的示例代碼類似，但如果有更多重複項需要更少的時間，並且如果數據已經排序或反向排序，則速度最快。主要區別在於使用修改後的Hoare分區方案（動態數據透視），中位數爲3來選擇初始數據透視。應該仍然存在導致最壞情況性能的模式，但我不確定這些模式會是什麼。

http://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme

void QuickSort(uint32_t a[], int lo, int hi) { 
    int i = lo, j = (lo + hi)/2, k = hi; 
    uint32_t pivot; 
    if (a[k] < a[i])   // median of 3 
     std::swap(a[k], a[i]); 
    if (a[j] < a[i]) 
     std::swap(a[j], a[i]); 
    if (a[k] < a[j]) 
     std::swap(a[k], a[j]); 
    pivot = a[j]; 
    while (i <= k) {   // partition 
     while (a[i] < pivot) 
      i++; 
     while (a[k] > pivot) 
      k--; 
     if (i <= k) { 
      std::swap(a[i], a[k]); 
      i++; 
      k--; 
     } 
    } 
    if (lo < k)     // recurse 
     QuickSort(a, lo, k); 
    if (i < hi) 
     QuickSort(a, i, hi); 
}