www说
//这是我的#include<fstream>#include<iostream>#include<cstdlib>//常用函数#include<windows.h>#include<time.h>#include<iomanip>//格式化输出using namespace std;int compare[7],change[7],move[7]; //compare数组是比较次数,change数组是交换次数,move数组是移动次数class SortableSList{public:SortableSList();void Reload(); //初始数据函数void Save_File(); //保存信息void InsertSort(); //直接插入排序void SelectSort(); //简单选择排序void BubbleSort(); //冒泡排序void QuickSort(); //快速排序void ShellSort(); //希尔排序void HeapSort(); //堆排序void MergeSort(); //两路合并排序void QuickSort(int left,int right);void PrintBeforeSort();void PrintAfterSort();private:int Partition(int left,int right);void InsSort(int h);void Merge(int left,int mid,int right);void Min(int i);int *l;int n;int *randarray;};SortableSList::SortableSList(){cout<<" | 请你输入要排序的数字个数 n : ";cin>>n;//输入要生成随机数的个数cout<<" | |"<<endl;cout<<" |----------------------------------------------------------------------------|"<<endl;cout<<" | |"<<endl;cout<<" | 请稍等...... |"<<endl;l=new int[n];randarray=new int[n];for(int i=0;i<n;i++) //随机产生1~10000的数字l[i]=randarray[i]=rand()%10000;}void SortableSList::Reload() //初始数据函数{int i;for(i=0;i<n;i++)l[i]=randarray[i];}void SortableSList::Save_File() //保存信息{int i;ofstream ofile("排序.txt");//文件输出流for(i=1;i<=n;i++)ofile<<l[i]<<" ";//读取文件ofile.close();ifstream infile("排序.txt");//输入文件对操作for(i=1;i<=n;i++)infile>>l[i];infile.close();}//~~~~~~~~~~~~~~~直接插入排序~~~~~~~~~~~~~~~~~~~void SortableSList::InsertSort(){int i,j;for(i=1;i<n;i++){int x=l[i];move[0]++;for(j=i-1;j>=0&&x<l[j];j--){compare[0]++;l[j+1]=l[j],change[0]++;move[0]++;}compare[0]++;l[j+1]=x;}}//~~~~~~~~~~~~~~~简单选择排序~~~~~~~~~~~~~~~~~~~~~void Swap(int&a,int&b){int e=a;a=b;b=e;}void SortableSList::SelectSort(){int s;for(int i=0;i<n-1;i++){s=i;compare[1]++;for(int j=i+1;j<n;j++)if(l[j]<l[s]) s=j;Swap(l[i],l[s]),move[1]=move[1]+3,change[1]++;}}//~~~~~~~~~~~~~~~快速排序~~~~~~~~~~~~~~~~~~~~~~~~~int SortableSList::Partition(int left,int right){int i=left,j=right+1;do{do{i++; compare[3]++;}while(l[i]<l[left]);do{j--; compare[3]++;}while(l[j]>l[left]);if(i<j) Swap(l[i],l[j]),change[3]++;}while(i<j);Swap(l[left],l[j]),move[3]=move[3]+3,change[3]++;return j;}void SortableSList::QuickSort(int left,int right){if(left<right){int j=Partition(left,right);QuickSort(left,j-1);QuickSort(j+1,right);}}void SortableSList::QuickSort(){QuickSort(0,n-1);}//******************希尔排序**********************void SortableSList::InsSort(int h){int i,j;int x;for(i=h;i<n;i+=h){x=l[i];move[4]++;compare[4]++;change[4]++;for(j=i-h;j>=0 && x<l[j];j-=h){compare[4]++;l[j+h]=l[j];change[4]++;move[4]++;}l[j+h]=x;move[4]++;}}void SortableSList::ShellSort(){int incr=n,i;do{incr=incr/3+1;for(i=0;i<incr;i++) InsSort(incr);}while(incr>1);}//~~~~~~~~~~~~~~~~~~~冒泡排序~~~~~~~~~~~~~~~~~~~~void SortableSList::BubbleSort(){int i=n-1,k=1,j,last;while(i>0){last=0;for(j=0;j<i;j++){compare[2]++;if(l[j+1]<l[j]){Swap(l[j],l[j+1]);last=j;}move[2]=move[2]+3; //2指各个排序算法的标号,3指移动次数}change[2]++;i=last;}}//~~~~~~~~~~~~~~~~~~~堆排序~~~~~~~~~~~~~~~~~~void SortableSList::Min(int i){int m = i;int s = i<<1;int t = (i<<1)+1;if(t>=n){compare[5]++;return ;}if(l[s]<l[m]){m = s;compare[5]++;change[5]++;}if(l[t]<l[m]){m = t;compare[5]++;change[5]++;}if(m!=i){move[5]++;swap(l[m],l[i]);Min(m);}}void SortableSList::HeapSort(){for(int i=(n>>1)-1;i>=0;i--){Min(i);}}//~~~~~~~~~~~~~~~~~~~两路合并排序~~~~~~~~~~~~~~~~~~void SortableSList::MergeSort(){int left,right,mid,size=1; //变量size是子序列的大小,初值为1while(size<n){left=0;while(left+size<n){mid=left+size-1;if(mid+size>n-1)right=n-1;else right=mid+size;Merge(left,mid,right);left=right+1;}size*=2; //每趟排序结束时size都乘2}}void SortableSList::Merge (int left,int mid,int right){int*temp=new int[right-left+1];int i=left,j=mid+1,k=0;while((i<=mid)&&(j<=right)){compare[6]++;if(l[i]<=l[j]) temp[k++]=l[i++],change[6]++;else temp[k++]=l[j++],move[6]++,change[6]++;}while(i<=mid) temp[k++]=l[i++],move[6]++,change[6]++; //将2个子序列 (l[left],...l[mid])和(l[mid+1],...l[right])//合并为一个有序子序列while(j<=right) temp[k++]=l[j++],move[6]++,change[6]++;for(i=0,k=left;k<=right;) l[k++]=temp[i++],move[6]++,change[6]++;}//~~~~~~~~~~~~~~~~~~~排序输出~~~~~~~~~~~~~~~~~~void SortableSList::PrintBeforeSort(){cout<<"排序前的数组:\n";for(int i=0;i<n;i++){cout<<randarray[i]<<" ";if((i+1)%10==0)cout<<endl;}}void SortableSList::PrintAfterSort(){cout<<"排序后的数组:\n";for(int i=0;i<n;i++){cout<<l[i]<<" ";if((i+1)%10==0)cout<<endl;}}int main(){int i,j;for(i=0;i<7;i++)//六种排序的循环{ compare[i]=change[i]=move[i]=0;}long int spendtime[7];int range[7];//排名long int t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11,t12,t13,t14;//起始时间,也就是当前时间int select;bool a=true;cout<<" *----------------------------------------------------------------------------*"<<endl;cout<<" | 各 种 内 排 序 算 法 的 性 能 比 较 |"<<endl;cout<<" |----------------------------------------------------------------------------|"<<endl;cout<<" | |"<<endl;cout<<" | 1-生成目标列表比较各个内排序算法 |"<<endl;cout<<" | |"<<endl;//cout<<" | 3-打印排序前和排序后的数组 |"<<endl;//cout<<" | |"<<endl;cout<<" | 2-退出系统 |"<<endl;cout<<" | |"<<endl;cout<<" |----------------------------------------------------------------------------|"<<endl;do{cout<<" | |"<<endl;cout<<" | 请输入你要选择的操作: ";cin>>select;cout<<" | |"<<endl;if(select==1){SortableSList d;d.Save_File();t1=GetTickCount();d.InsertSort ();t2=GetTickCount();d.Reload();t3=GetTickCount();d.SelectSort ();t4=GetTickCount();d.Reload();t5=GetTickCount();d.BubbleSort ();t6=GetTickCount();d.Reload();//恢复到初始数据函数t7=GetTickCount();d.QuickSort ();t8=GetTickCount();d.Reload();t9=GetTickCount();d.ShellSort ();t10=GetTickCount();d.Reload();t11=GetTickCount();d.HeapSort();t12=GetTickCount();d.Reload();t13=GetTickCount();d.MergeSort();t14=GetTickCount();spendtime[0]=t2-t1;spendtime[1]=t4-t3;spendtime[2]=t6-t5;spendtime[3]=t8-t7;spendtime[4]=t10-t9;spendtime[5]=t12-t11;spendtime[6]=t14-t13;for(i=0;i<7;i++)//根据花费时间进行排名{int t=1;for(j=0;j<7;j++){if(i!=j)if(spendtime[i]>spendtime[j]) t++;}range[i]=t;}cout<<" | |"<<endl;cout<<" | 总共用时: 约为"<<setw(5)<<spendtime[0]+spendtime[1]+spendtime[2]+spendtime[3]+spendtime[4]<<"毫秒 |"<<endl;cout<<" |----------------------------------------------------------------------------|"<<endl;cout<<" | --- 结 果 如 下 --- |"<<endl;cout<<" |----------------------------------------------------------------------------|"<<endl;cout<<" |排序的名称"<<setw(3)<<"| 比较次数"<<setw(3)<<"|交换的次数"<<setw(3)<<"|移动的次数"<<setw(3)<<"| 时间(ms) "<<"| 时间排名 "<<setw(3)<<"| 时间复杂度|"<<endl;cout<<" |----------+---------+----------+----------+----------+----------+-----------|"<<endl;cout<<" | 插入排序 |"<<setw(8)<<compare[0]<<" |"<<setw(8)<<change[0]<<" |"<<setw(9)<<move[0]<<" |"<<setw(8)<<spendtime[0]<<" |"<<setw(8)<<range[0]<<" |"<<setw(11)<<" n*n |"<<endl;cout<<" |----------+---------|----------+----------+----------+----------+-----------|"<<endl;cout<<" | 选择排序 |"<<setw(8)<<compare[1]<<" |"<<setw(8)<<change[1]<<" |"<<setw(9)<<move[1]<<" |"<<setw(8)<<spendtime[1]<<" |"<<setw(8)<<range[1]<<" |"<<setw(11)<<" n*n |"<<endl;cout<<" |----------+---------|----------+----------+----------+----------+-----------|"<<endl;cout<<" | 冒泡排序 |"<<setw(8)<<compare[2]<<" |"<<setw(8)<<change[2]<<" |"<<setw(9)<<move[2]<<" |"<<setw(8)<<spendtime[2]<<" |"<<setw(8)<<range[2]<<" |"<<setw(11)<<" n*n |"<<endl;cout<<" |----------+---------|----------+----------+----------+----------+-----------|"<<endl;cout<<" | 快速排序 |"<<setw(8)<<compare[3]<<" |"<<setw(8)<<change[3]<<" |"<<setw(9)<<move[3]<<" |"<<setw(8)<<spendtime[3]<<" |"<<setw(8)<<range[3]<<" |"<<setw(11)<<" n*log2n |"<<endl;cout<<" |----------+---------|----------+----------+----------+----------+-----------|"<<endl;cout<<" | 希尔排序 |"<<setw(8)<<compare[4]<<" |"<<setw(8)<<change[4]<<" |"<<setw(9)<<move[4]<<" |"<<setw(8)<<spendtime[4]<<" |"<<setw(8)<<range[4]<<" |"<<setw(11)<<" n*log2n |"<<endl;cout<<" |----------+---------|----------+----------+----------+----------+-----------|"<<endl;cout<<" | 堆排序 |"<<setw(8)<<compare[5]<<" |"<<setw(8)<<change[5]<<" |"<<setw(9)<<move[5]<<" |"<<setw(8)<<spendtime[5]<<" |"<<setw(8)<<range[5]<<" |"<<setw(11)<<" n*log2n |"<<endl;cout<<" *----------------------------------------------------------------------------*"<<endl;cout<<" | 合并排序 |"<<setw(8)<<compare[6]<<" |"<<setw(8)<<change[6]<<" |"<<setw(9)<<move[6]<<" |"<<setw(8)<<spendtime[6]<<" |"<<setw(8)<<range[6]<<" |"<<setw(11)<<" n*log2n |"<<endl;cout<<" *----------------------------------------------------------------------------*"<<endl;a=true;cout<<"\n是否打印排序前和排序后的队列(选1 打印 或 选2 返回)\n";int sel;cin>>sel;if(sel==1){d.PrintBeforeSort();d.PrintAfterSort();}else if(sel==2){continue;}}else if(select==2){cout<<" *----------------------------------------------------------------------------*"<<endl;cout<<" | --- 程 序 结 束 --- |"<<endl;cout<<" *----------------------------------------------------------------------------*"<<endl;a=false;}else{cout<<" | 你的输入有错误,请重新输入! |"<<endl;cout<<" | |"<<endl;a=true;}}while(a==true);return 0;}