C++中十种内部排序算法的比较分析
C++中十种内部排序算法的比较分析
#include<iostream> #include<ctime> #include<fstream> usingnamespacestd; #defineMAXSIZE1000//可排序表的最大长度 #defineSORTNUM10//测试10中排序方法 #definemax100//基数排序时数据的最大位数不超过百位; typedefstructnode{ intdata3; intnext; }node; typedefintDataType[MAXSIZE+2]; DataTypedata; DataTypedata2; DataTypeR1; intsize;//可排序表的长度 inthead; intfr[10]; intre[10]; longcompCount;//统计比较次数 longshiftCount;//统计移动次数 voidBeforeSort()//对比较次数和移动次数清零 { compCount=0; shiftCount=0; } boolLess(inti,intj)//若表中第i个元素小于第j个元素,则返回True,否则返回False { compCount++; returndata[i]<data[j]; } voidSwap(inti,intj)//交换表中第i个和第j个元素 { inta; a=data[i]; data[i]=data[j]; data[j]=a; shiftCount=shiftCount+3; } voidShift(DataType&R,DataType&R2,inti,intj)//将R2[j]赋给R[i] { R[i]=R2[j]; shiftCount++; } voidCopyData(DataTypelist1,DataTypelist2) { inti; for(i=1;i<=size;i++)list2[i]=list1[i]; } voidInverseOrder()//将可排序表置为逆序 { inti,j; for(i=1,j=size;i<=size/2;i++,j--) { inta; a=data[i]; data[i]=data[j]; data[j]=a; } CopyData(data,data2); } voidRandomizeList()//由系统随机一组数 { inti; srand(time(0)); for(i=1;i<=size;i++) data[i]=rand()%(size+1); CopyData(data,data2); ofstreamout_stream; out_stream.open("input.txt",ios::app); if(out_stream.fail()) { cout<<"inputfileopeningfailed.\n"; exit(1); } for(i=1;i<=size;i++)out_stream<<data[i]<<""; out_stream<<"\n"; out_stream.close(); } voidRecallList()//恢复最后一次用RandomizeList随机打乱的可排序表 { CopyData(data2,data); } voidoutput()//输出函数 { ofstreamout_stream; cout<<"\t"<<compCount<<"\t\t"<<shiftCount<<"\n"; out_stream.open("output.txt",ios::app); if(out_stream.fail()) { cout<<"Outputfileopeningfailed.\n"; exit(1); } out_stream<<"\t"<<compCount<<"\t\t"<<shiftCount<<"\n"; out_stream.close(); } voidBubbleSort()//冒泡排序 { BeforeSort(); intswapped,i,m; m=size-1; do{ swapped=0; for(i=1;i<=m;i++) { if(Less(i+1,i)) { Swap(i+1,i); swapped=1; } } m--; }while(swapped); output(); } voidInsertSort()//插入排序 { BeforeSort(); inti,j; for(i=2;i<=size;i++) { Shift(data,data,0,i); j=i-1; while(Less(0,j)) { Shift(data,data,j+1,j); j--; } Shift(data,data,j+1,0); } output(); } voidSelectSort()//选择排序 { BeforeSort(); inti,j,min; for(i=1;i<=size-1;i++) { min=i; for(j=i+1;j<=size;j++) if(Less(j,min))min=j; if(i!=min)Swap(i,min); } output(); } intPartition(intlow,inthigh) { intpivotkey; Shift(data,data,0,low); pivotkey=data[low]; while(low<high) { compCount++; while(low<high&&data[high]>=pivotkey){compCount++;--high;} Shift(data,data,low,high); compCount++; while(low<high&&data[low]<=pivotkey){compCount++;++low;} Shift(data,data,high,low); } Shift(data,data,low,0); returnlow; } voidQSort(intlow,inthigh)//QuickSort的辅助函数 { intpivotloc; if(low<high) { pivotloc=Partition(low,high); QSort(low,pivotloc-1); QSort(pivotloc+1,high); } } voidQuickSort()//快速排序 { BeforeSort(); QSort(1,size); output(); } voidShellSort()//希尔排序 { BeforeSort(); inti,j,h; i=4; h=1; while(i<=size) { i=i*2; h=2*h+1; } while(h!=0) { i=h; while(i<=size) { j=i-h; while(j>0&&Less(j+h,j)) { Swap(j,j+h); j=j-h; } i++; } h=(h-1)/2; } output(); } voidSift(intleft,intright)//堆排序的调堆函数 { inti,j,finished=0; i=left; j=2*i; Shift(data,data,0,left); Shift(data,data,MAXSIZE+1,left); while(j<=right&&!finished) { if(j<right&&Less(j,j+1))j=j+1; if(!Less(0,j))finished=1; else { Shift(data,data,i,j); i=j; j=2*i; } } Shift(data,data,i,MAXSIZE+1); } voidHeapSort()//堆排序 { intleft,right; BeforeSort(); for(left=size/2;left>=1;left--)Sift(left,size); for(right=size;right>=2;right--) { Swap(1,right); Sift(1,right-1); } output(); } voidBInsertSort()//折半插入排序 { BeforeSort(); inti,low,high,m,j; for(i=2;i<=size;i++) { Shift(data,data,0,i); low=1; high=i-1; while(low<=high) { m=(low+high)/2; if(Less(0,m))high=m-1; elselow=m+1; } for(j=i-1;j>=high+1;j--)Shift(data,data,j+1,j); Shift(data,data,high+1,0); } output(); } voidBinsort()//2-路插入排序 { BeforeSort(); inti,k,j; intfirst,last; first=last=1; Shift(R1,data,1,1); for(i=2;i<=size;i++) { compCount++; if(data[i]>=R1[1]) { compCount++; j=last; while(j>=1&&R1[j]>data[i]) { Shift(R1,R1,j+1,j); j--; compCount++; } Shift(R1,data,j+1,i); last++; } else { first--; if(first==0)first=size; j=first+1; compCount++; while(j<=size&&R1[j]<=data[i]) { Shift(R1,R1,j-1,j); j++; compCount++; } Shift(R1,data,j-1,i); } } k=1; j=first; while(k<=size) { Shift(data,R1,k,j); k++; j=(j+1)%(size+1); if(j==0)j=j+1; } output(); } voidMerge(intlow,intm,inthigh) { inti=low,j=m+1,p=1; while(i<=m&&j<=high) { if(Less(i,j))Shift(R1,data,p++,i++); elseShift(R1,data,p++,j++); } while(i<=m) Shift(R1,data,p++,i++); while(j<=high) Shift(R1,data,p++,j++); for(p=1,i=low;i<=high;p++,i++) Shift(data,R1,i,p); } voidMSort(intlow,inthigh) { intmid; if(low<high){ mid=(low+high)/2; MSort(low,mid); MSort(mid+1,high); Merge(low,mid,high); } } voidMergeSort()//归并排序 { BeforeSort(); MSort(1,size); output(); } voidDistribute(node*a,intw) { inti; for(i=0;i<10;i++)fr[i]=-1; for(i=head;i!=-1;i=a[i].next) { intx=a[i].data3/w%10; if(fr[x]==-1) { fr[x]=re[x]=i; compCount++; } else { a[re[x]].next=i; re[x]=i; shiftCount++; } } for(i=0;i<10;i++) { if(fr[i]!=-1) { a[re[i]].next=-1; } } } voidCollect(node*a) { inti,last; last=-1; for(i=0;i<10;i++) { if(fr[i]!=-1) { if(last==-1) { head=fr[i]; last=re[i]; } else{ a[last].next=fr[i]; last=re[i]; shiftCount++; } } } a[last].next=-1; } voidRadixSort()//基数排序算法。 { BeforeSort(); ofstreamout_stream; node*a; a=newnode[size]; inti,j=1; for(i=0;i<size;i++){ a[i].data3=data[i+1]; a[i].next=i+1; } head=0; a[size-1].next=-1; for(i=1;i<=max;i*=10){ Distribute(a,i); Collect(a); } cout<<"\t"<<compCount<<"\t\t"<<shiftCount<<"\n"; while(head!=-1) { data[j++]=a[head].data3; head=a[head].next; } CopyData(data,data2); cout<<"\n"; out_stream.open("output.txt",ios::app); out_stream<<"\t"<<compCount<<"\t\t"<<shiftCount<<"\n\n"; out_stream.close(); } voidInitialization()//系统初始化 { system("cls");//清屏 cout<<"***************************************************************************\n" <<"*****************《内部排序算法的比较》********************************\n" <<"***************************************************************************\n" <<"*************************主菜单****************************************\n" <<"*******1.由系统随机产生待排序表****************************************\n" <<"*******2.手动输入待排序表**********************************************\n" <<"*******3.返回主菜单****************************************************\n" <<"*******4.退出程序******************************************************\n" <<"***************************************************************************\n" <<"请输入要执行的步骤:"; } voidInterpret(intcmd)//调用各个算法 { inti,j,m; ofstreamout_stream; out_stream.open("output.txt",ios::app); if(out_stream.fail()) { cout<<"Outputfileopeningfailed.\n"; exit(1); } switch(cmd) { case1: out_stream<<"由系统随机产生待排序表的各个算法的比较次数和移动次数如下:\n"; out_stream<<"\tcompCount\tshiftCount\n"; out_stream.close(); cout<<"请输入待排序表的长度:"; cin>>size; cout<<"由系统随机产生待排序表的各个算法的比较次数和移动次数如下:\n"; RandomizeList(); for(m=0;m<3;m++) { if(m==2)InverseOrder(); cout<<"\t"; for(i=1;i<=size;i++)cout<<data[i]<<""; cout<<"\n"; cout<<"\tcompCount\tshiftCount\n"; for(j=0;j<SORTNUM;j++) { RecallList(); out_stream.open("output.txt",ios::app); if(j==0){cout<<"Bubbl:";out_stream<<"Bubbl:";out_stream.close();BubbleSort();} if(j==1){cout<<"Tnser:";out_stream<<"Tnser:";out_stream.close();InsertSort();} if(j==2){cout<<"Selec:";out_stream<<"Selec:";out_stream.close();SelectSort();} if(j==3){cout<<"Quick:";out_stream<<"Quick:";out_stream.close();QuickSort();} if(j==4){cout<<"Shell:";out_stream<<"Shell:";out_stream.close();ShellSort();} if(j==5){cout<<"Heap:";out_stream<<"Heap:";out_stream.close();HeapSort();} if(j==6){cout<<"BInse:";out_stream<<"BInse:";out_stream.close();BInsertSort();} if(j==7){cout<<"Merge:";out_stream<<"Merge:";out_stream.close();MergeSort();} if(j==8){cout<<"Bin:";out_stream<<"Bin:";out_stream.close();Binsort();} if(j==9){cout<<"Radix:";out_stream<<"Radix:";out_stream.close();RadixSort();} }} //} break; case2: cout<<"请输入待排序表的长度:"; cin>>size; cout<<"请输入"<<size<<"个数据:\n"; for(i=1;i<=size;i++)cin>>data[i]; CopyData(data,data2); out_stream<<"手动输入待排序表的各个算法的比较次数和移动次数如下:\n"; out_stream<<"\tcompCount\tshiftCount\n"; out_stream.close(); cout<<"手动输入待排序表的各个算法的比较次数和移动次数如下:\n"; cout<<"\tcompCount\tshiftCount\n"; for(j=0;j<SORTNUM;j++) { RecallList(); out_stream.open("output.txt",ios::app); if(j==0){cout<<"Bubbl:";out_stream<<"Bubbl:";out_stream.close();BubbleSort();} if(j==1){cout<<"Tnser:";out_stream<<"Tnser:";out_stream.close();InsertSort();} if(j==2){cout<<"Selec:";out_stream<<"Selec:";out_stream.close();SelectSort();} if(j==3){cout<<"Quick:";out_stream<<"Quick:";out_stream.close();QuickSort();} if(j==4){cout<<"Shell:";out_stream<<"Shell:";out_stream.close();ShellSort();} if(j==5){cout<<"Heap:";out_stream<<"Heap:";out_stream.close();HeapSort();} if(j==6){cout<<"BInse:";out_stream<<"BInse:";out_stream.close();BInsertSort();} if(j==7){cout<<"Merge:";out_stream<<"Merge:";out_stream.close();MergeSort();} if(j==8){cout<<"Bin:";out_stream<<"Bin:";out_stream.close();Binsort();} if(j==9){cout<<"Radix:";out_stream<<"Radix:";out_stream.close();RadixSort();} } break; case3: Initialization(); break; } } voidmain() { Initialization(); intcmd; do{ cin>>cmd; Interpret(cmd); }while(cmd!=4); }
以上就是本文所述的全部内容了,希望能够对大家熟悉掌握这十种排序算法有所帮助。