C++快速排序運行時間

Question

我有一個關於快速排序算法的問題。我執行快速排序算法並播放它。 初始未排序數組中的元素是從特定範圍中選擇的隨機數。 我發現隨機數的範圍影響運行時間。例如，從範圍（1 - 2000）中選擇的1,000,000個隨機數的運行時間需要40秒。如果從範圍（1 - 10,000）中選擇1,000,000個號碼，則需要9秒。 但我不知道如何解釋它。在課堂上，我們討論樞軸值會影響遞歸樹的深度。
對於我的實現，數組的最後一個值被選爲樞軸值。我不使用隨機方案來選擇樞軸值。

int partition(vector<int> &vec, int p, int r) { 

    int x = vec[r]; 
    int i = (p-1); 
    int j = p; 
    while(1) { 

    if (vec[j] <= x){ 
     i = (i+1); 
     int temp = vec[j]; 
     vec[j] = vec[i]; 
     vec[i] = temp; 
    } 
    j=j+1; 
    if (j==r) 
     break; 
} 
    int temp = vec[i+1]; 
    vec[i+1] = vec[r]; 
    vec[r] = temp; 
    return i+1; 
} 

void quicksort (vector<int> &vec, int p, int r) { 

    if (p<r){ 
    int q = partition(vec, p, r); 
    quicksort(vec, p, q-1); 
    quicksort(vec, q+1, r); 
    } 
} 

    void random_generator(int num, int * array) { 

     srand((unsigned)time(0)); 
     int random_integer; 
     for(int index=0; index< num; index++){ 
     random_integer = (rand()%10000)+1; 
     *(array+index) = random_integer; 
     } 
    } 

    int main() { 
     int array_size = 1000000; 
     int input_array[array_size]; 
     random_generator(array_size, input_array); 
     vector<int> vec(input_array, input_array+array_size); 

     clock_t t1, t2; 
     t1 = clock(); 
     quicksort(vec, 0, (array_size - 1)); // call quick sort 
     int length = vec.size(); 
     t2 = clock(); 
     float diff = ((float)t2 - (float)t1); 
     cout << diff << endl; 
     cout << diff/CLOCKS_PER_SEC <<endl; 
    } 

Answer 1

最有可能的是它不能很好地執行，因爲快速排序不能很好地處理大量重複項，並且仍然可能導致交換它們（不能保證鍵等同元素的順序不會被保留）。您會注意到，每個數字的重複次數爲10000,100或2000，而時間因素也大約爲5的因子。

您是否將運行時間的平均值分別至少5-10次大小，以獲得一個良好的開始關鍵的公平鏡頭？

作爲一個比較，你檢查了std :: sort和std :: stable_sort如何在同一個數據集上執行？

最後對於這種數據分佈（除非這是一個快速排序練習），我認爲計數排序會好得多 - 40K內存來存儲計數，它運行在O（n）。

Answer 2

它可能與如何很好地對輸入進行排序有關。如果輸入是合理隨機的，則快速排序爲O（n logn）。如果它的順序相反，性能可能會降低到O（n^2）。數據範圍越小，您可能越接近O（n^2）行爲。