习题1.6.3
对比系统自带的排序(这里使用STL中的sort函数)、使用位图排序和冒泡排序。输入是txt文本,使用生成的随机数序列。
测试代码如下:
#include <iostream> #include <algorithm> #include <fstream> #include <cstdlib> #include <ctime> #include <bitset> using namespace std; void readData(int a[], int n, const string & file) { ifstream in(file.c_str()); int i=0; while(i<n) { in>>a[i]; i++; } in.close(); } void saveDate(int a[], int n, const string & file) { ofstream o(file.c_str()); int i=0; while(i<n) { o<<a[i]<<"\n"; i++; } o.close(); } void sysSort(int a[], int n) { sort(a,a+n); ofstream o("ss.txt"); int i=0; while(i<n) { o<<a[i]<<"\n"; i++; } o.close(); } void BubleSort(int a[], int n) { for(int i=0; i<n; i++) { bool flag=false; for(int j=0; j<n-i-1; j++) { if(a[j]>a[j+1]) { swap(a[j],a[j+1]); flag = true; } } if(flag==false) break; } ofstream o("bs.txt"); int i=0; while(i<n) { o<<a[i]<<"\n"; i++; } o.close(); } void mySort(int a[], int n) { const int Base = 1000000;///所有的7位数都减去1000000,即前Base位不用,所以节省这么多内存位 const int Range = 10000000 - Base; //BitMap bm(Range); bitset<Range> bm; for(int i=0;i<n;i++) { bm.set(a[i]-Base); } ///save data ofstream o("ms.txt"); for(int i=0;i<Range;i++) { if(bm.test(i)) o<<i+Base<<"\n"; } o.close(); } int main() { const int N = 8000000;///需要排序的数的个数 int * a = new int[N](); readData(a,N,"d.txt"); ///start time_t cs=time(0); sysSort(a,N); time_t cd=time(0); cout<<"sys sort time: "<<cd-cs<<" s."<<endl; readData(a,N,"d.txt"); ///start cs=time(0); mySort(a,N); cd=time(0); cout<<"my sort time: "<<cd-cs<<" s."<<endl; readData(a,N,"d.txt"); ///start //int b[] = {1,6,2,0,3,77,8,11}; cs=time(0); BubleSort(a,N); cd=time(0); cout<<"buble sort time: "<<cd-cs<<" s."<<endl; delete [] a; return 0; }
测试结果:
sys sort time: 6 s. my sort time: 3 s.
当N=8000000时,等了10多分钟,还没结束。i3的处理器一个核一直以接近满负荷运行,直接中断退出了。
把N设置为N=80000时的结果:
sys sort time: 0 s. my sort time: 0 s. buble sort time: 39 s. Process returned 0 (0x0) execution time : 43.309 s Press any key to continue.
难怪N=8000000时半天还没结束。。。。8万个数据排序居然要39秒。。。。龟速
可以看出,当数据量比较大时,冒泡排序性能急剧下降。。。
但是我很奇怪的是,stl中的sort为什么效率那么高??
仅仅比位图排序的时间大一倍而已,也就是说在同一个数量级上。