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）行为。