我正在对quicksort(来自c++ STL的qsort)算法进行分析,代码为:
#include <iostream>
#include <fstream>
#include <ctime>
#include <bits/stdc++.h>
#include <cstdlib>
#include <iomanip>
#define MIN_ARRAY 256000
#define MAX_ARRAY 1000000000
#define MAX_RUNS 100
using namespace std;
int* random_array(int size) {
int* array = new int[size];
for (int c = 0; c < size; c++) {
array[c] = rand()*rand() % 1000000;
}
return array;
}
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int main()
{
ofstream fout;
fout.open("data.csv");
fout << "array size,";
srand(time(NULL));
int size;
int counter = 1;
std::clock_t start;
double duration;
for (size = MIN_ARRAY; size < MAX_ARRAY; size *= 2) {
fout << size << ",";
}
fout << "\n";
for (counter = 1; counter <= MAX_RUNS; counter++) {
fout << "run " << counter << ",";
for (size = MIN_ARRAY; size < MAX_ARRAY; size *= 2) {
try {
int* arr = random_array(size);
start = std::clock();
qsort(arr, size, sizeof(int), compare);
duration = (std::clock() - start) / (double)CLOCKS_PER_SEC;
//cout << "size: " << size << " duration: " << duration << '\n';
fout << setprecision(15) << duration << ",";
delete[] arr;
}
catch (bad_alloc) {
cout << "bad alloc caught, size: " << size << "\n";
fout << "bad alloc,";
}
}
fout << "\n";
cout << counter << "% done\n";
}
fout.close();
return 0;
}
当我运行它时,数据完全线性地返回:这到底是怎么回事?快速排序不是 O(nlogn) 吗?
这是使用的数组大小以及所有 100 次运行的每个大小的平均时间(以秒为单位):
arraysize,256000,512000,1024000,2048000,4096000,8192000,16384000,32768000,65536000,131072000,262144000,524288000
average,0.034,0.066,0.132,0.266,0.534,1.048,2.047,4.023,7.951,15.833,31.442
最佳答案
关于c++ - 快速排序线性时间?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/66660409/