我有一个关于快速排序算法的问题。我实现了快速排序算法并播放它。
初始未排序数组中的元素是从一定范围内选择的随机数。
我发现随机数的范围会影响运行时间。例如,从范围 (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;
}
最佳答案
很可能它表现不佳,因为快速排序不能很好地处理大量重复项,并且可能仍会导致交换它们(不保证保留键相等元素的顺序)。您会注意到每个数字的重复次数对于 10000 为 100 或对于 2000 为 500,而时间因子也大约为 5 倍。
您是否对每个大小的至少 5-10 次运行的运行时间进行了平均,以公平地获得良好的起始点?
作为比较,您是否检查过 std::sort 和 std::stable_sort 在相同数据集上的表现如何?
最后,对于这种数据分布(除非这是一个快速排序练习),我认为计数排序会好得多 - 40K 内存来存储计数并且它在 O(n) 中运行。
关于C++快速排序运行时间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2737541/