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); }以上就是本文所述的全部內容了，希望能夠對大家熟悉掌握這十種排序算法有所幫助。
新聞熱點
疑難解答
圖片精選
