C++中十种内部排序算法的比较分析

#include<iostream>#include<ctime>#include<fstream> using namespace std;#define MAXSIZE 1000 //可排序表的最大长度#define SORTNUM 10 //测试10中排序方法#define max 100 //基数排序时数据的最大位数不超过百位； typedef struct node { int data3; int next;} node;typedef int DataType[MAXSIZE+2];DataType data;DataType data2;DataType R1;int size;//可排序表的长度int head;int fr[10];int re[10];long compCount;//统计比较次数long shiftCount;//统计移动次数 void BeforeSort()//对比较次数和移动次数清零 { compCount=0; shiftCount=0; } bool Less(int i,int j)//若表中第i个元素小于第j个元素，则返回True，否则返回False { compCount++; return data[i]<data[j]; } void Swap(int i,int j)//交换表中第i个和第j个元素 { int a; a=data[i]; data[i]=data[j]; data[j]=a; shiftCount=shiftCount+3; } void Shift(DataType &R,DataType &R2,int i,int j)//将R2[j]赋给R[i] { R[i]=R2[j]; shiftCount++; } void CopyData(DataType list1,DataType list2) { int i; for(i=1;i<=size;i++) list2[i]=list1[i]; } void InverseOrder()//将可排序表置为逆序 { int i,j; for(i=1,j=size;i<=size/2;i++,j--) { int a; a=data[i]; data[i]=data[j]; data[j]=a; } CopyData(data,data2); } void RandomizeList()//由系统随机一组数 { int i; srand(time(0)); for(i=1;i<=size;i++) data[i]=rand()%(size+1); CopyData(data,data2); ofstream out_stream; out_stream.open("input.txt",ios::app); if(out_stream.fail()) { cout<<"input file opening failed.\n"; exit(1); } for(i=1;i<=size;i++) out_stream<<data[i]<<" "; out_stream<<"\n"; out_stream.close(); } void RecallList()//恢复最后一次用RandomizeList随机打乱的可排序表 { CopyData(data2,data); } void output()//输出函数 { ofstream out_stream; cout<<"\t"<<compCount<<"\t\t"<<shiftCount<<"\n"; out_stream.open("output.txt",ios::app); if(out_stream.fail()) { cout<<"Output file opening failed.\n"; exit(1); } out_stream<<"\t"<<compCount<<"\t\t"<<shiftCount<<"\n"; out_stream.close(); } void BubbleSort()//冒泡排序 { BeforeSort(); int swapped,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(); } void InsertSort() //插入排序 { BeforeSort(); int i,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(); } void SelectSort()//选择排序 { BeforeSort(); int i,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(); } int Partition(int low,int high) { int pivotkey; 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); return low; } void QSort(int low,int high)//QuickSort的辅助函数 { int pivotloc; if(low<high) { pivotloc=Partition(low,high); QSort(low,pivotloc-1); QSort(pivotloc+1,high); } } void QuickSort()//快速排序 { BeforeSort(); QSort(1,size); output(); } void ShellSort()//希尔排序 { BeforeSort(); int i,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(); } void Sift(int left,int right)//堆排序的调堆函数 { int i,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); } void HeapSort()//堆排序 { int left,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(); } void BInsertSort()//折半插入排序{ BeforeSort(); int i,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; else low=m+1; } for(j=i-1;j>=high+1;j--) Shift(data,data,j+1,j); Shift(data,data,high+1,0); } output();} void Binsort()//2-路插入排序{ BeforeSort(); int i,k,j; int first,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();} void Merge(int low,int m,int high){ int i=low,j=m+1,p=1; while(i<=m&&j<=high) { if(Less(i,j)) Shift(R1,data,p++,i++); else Shift(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); } void MSort(int low, int high) { int mid; if (low<high){ mid=(low+high)/2; MSort(low, mid); MSort(mid+1,high); Merge(low, mid, high); } } void MergeSort()//归并排序{ BeforeSort(); MSort(1,size); output();} void Distribute(node *a, int w){ int i; for (i=0; i<10; i++) fr[i] = -1; for (i=head; i!=-1; i=a[i].next) { int x = 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; } }} void Collect(node *a){ int i, 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;} void RadixSort()//基数排序算法。{ BeforeSort(); ofstream out_stream; node* a; a=new node[size]; int i,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(); } void Initialization()//系统初始化{ system("cls");//清屏 cout<<"***************************************************************************\n" <<"***************** 《内部排序算法的比较》 ********************************\n" <<"***************************************************************************\n" <<"************************ *主菜单* ***************************************\n" <<"******* 1.由系统随机产生待排序表 ****************************************\n" <<"******* 2.手动输入待排序表 **********************************************\n" <<"******* 3.返回主菜单 ****************************************************\n" <<"******* 4.退出程序 ******************************************************\n" <<"***************************************************************************\n" <<"请输入要执行的步骤：";} void Interpret(int cmd)//调用各个算法 { int i,j,m; ofstream out_stream; out_stream.open("output.txt",ios::app); if(out_stream.fail()) { cout<<"Output file opening failed.\n"; exit(1); } switch(cmd) { case 1: 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; case 2: 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; case 3: Initialization(); break; } } void main() { Initialization(); int cmd; do{ cin>>cmd; Interpret(cmd); }while(cmd!=4); }

以上就是本文所述的全部内容了，希望能够对大家熟悉掌握这十种排序算法有所帮助。