我写的代码:
#include <iostream>
using namespace std;
#include <vector>
#include <list>
#include <algorithm>
int main()
{const int N = 10000000;vector<int> v;list<int> l;for (int i = 0; i < N; i++){v.push_back(i);l.push_back(i);}int begin1 = clock();sort(v.begin(), v.end());int end1 = clock();int begin2 = clock();l.sort();int end2 = clock();cout << "vector+算法:" << end1 - begin1 << endl;cout << "list+sort:" << end2 - begin2 << endl;
}
运行结果:无论N为多大,上面永远大于下面
老师的代码:
#include <time.h>
#include <iostream>
using namespace std;
#include <list>
#include <vector>
#include <algorithm>int main()
{srand(time(0));const int N = 10000000;vector<int> v;v.reserve(N);list<int> lt2;for (int i = 0; i < N; i++){auto e = rand();v.push_back(e);lt2.push_back(e);}int begin1 = clock();sort(v.begin(), v.end());int end1 = clock();int begin2 = clock();lt2.sort();int end2 = clock();cout << "vector sort:" << end1 - begin1 << endl;cout << "list sort:" << end2 - begin2 << endl;
}
运行结果:N较小时,差不多大,N较大时,上面比小面小得多
原因:
快排在最坏情况下的时间复杂度为(n^2),最坏情况对应的是数据有序,我写的代码就是有序数,所有跑出来的结果和老师的无序数相反,快排的平均时间复杂度是(nlgn),快排只有在无序数中排序才有意义