常见排序算法的实现与性能比较

#include"stdlib.h" #include"iostream.h" #include"time.h" #include<malloc.h> typedef struct node{ int key; struct node * next; }KeyNode; //定义桶的结构 /*各种排序算法的声明*/ void show(); void compare(int k,int *c,int n); void insertSort(int *c,int n) { clock_t start,finish; //定义时间 double totaltime; start=clock();// 开始时间 /* --------------算法操作------------*/ for (int i = 1; i < n; i++) { int t = c[i]; int j = i; while ((j > 0) && (c[j - 1] > t)) { c[j] = c[j - 1];//交换顺序 --j; } c[j] = t; } /* --------------算法操作------------*/ finish=clock(); if(n==10){ //n 是10 的时候输出排序结果 for(int v=0;v<n;v++) cout<<c[v]<<" "; }else { totaltime=(double)(finish-start)/CLOCKS_PER_SEC;//计算工作时间 cout<<"此程序的运行时间为:"<<totaltime<<"秒!"<<endl; } } void ModInssort(int *c,int n,int delta)//一步希尔排序； { int temp; for(int i=delta;i<n;i+=delta) for(int j=i;j>=delta;j-=delta) { if(c[j]<c[j-delta]) { temp=c[i]; c[i]=c[j-delta]; c[j-delta]=temp; } else break; } } void sheerSort(int *c,int n) { clock_t start,finish; //定义时间 double totaltime; start=clock();// 开始时间 /* --------------算法操作------------*/ for(int delta=n/2;delta>0;delta/=2) for(int i=0;i<delta;i++) ModInssort(&c[i],n-i,delta); ModInssort(c,n,1); /* --------------算法操作------------*/ finish=clock(); if(n==10){ //n 是10 的时候输出排序结果 for(int v=0;v<n;v++) cout<<c[v]<<" "; }else { totaltime=(double)(finish-start)/CLOCKS_PER_SEC;//计算工作时间 cout<<"此程序的运行时间为:"<<totaltime<<"秒!"<<endl; } } void quicksort(int *c,int left,int right) { int i=left,j=right;int temp=c[i]; while(i<j) { while ((c[j]>temp)&&(j>i)) j=j-1; if (j>i) { c[i]=c[j];i=i+1; } while ((c[i]<=temp)&&(j>i)) i=i+1; if (i<j) {c[j]=c[i]; j=j-1; } } c[i]=temp; if (left<i-1) quicksort(c,left,i-1); if (i+1<right) quicksort(c,i+1,right); } void fastSort(int *c,int n) { clock_t start,finish; //定义时间 double totaltime; start=clock();// 开始时间 /* --------------算法操作------------*/ quicksort(c,0,n-1); /* --------------算法操作------------*/ finish=clock(); if(n==10){ //n 是10 的时候输出排序结果 for(int v=0;v<n;v++) cout<<c[v]<<" "; }else { totaltime=(double)(finish-start)/CLOCKS_PER_SEC;//计算工作时间 cout<<"此程序的运行时间为:"<<totaltime<<"秒!"<<endl; } } void bubbleSort(int *c,int n) { clock_t start,finish; //定义时间 double totaltime; start=clock();// 开始时间 /* --------------算法操作------------*/ bool Noswap; int temp; for(int i=0;i<n;i++) { Noswap=true; for(int j=n-1;j>i;j--) { if(c[j]<c[j-1]) { temp=c[j]; c[j]=c[j-1]; c[j-1]=temp; Noswap=false; } } } /* --------------算法操作------------*/ finish=clock(); if(n==10){ //n 是10 的时候输出排序结果 for(int v=0;v<n;v++) cout<<c[v]<<" "; }else { totaltime=(double)(finish-start)/CLOCKS_PER_SEC;//计算工作时间 cout<<"此程序的运行时间为:"<<totaltime<<"秒!"<<endl; } } void Merge(int *c,int *d,int l,int m,int r) { int i=l,j=m+1,k=l; while((i<=m)&&(j<=r)) if(c[i]<=c[j]) d[k++]=c[i++]; else d[k++]=c[j++]; if(i>m) for(int q=j;q<=r;q++) d[k++]=c[q]; else for(int q=i;q<=m;q++) d[k++]=c[q]; } void MergePass(int *x,int *y,int s,int n) { int i=0; while (i<=n-2*s) { Merge(x,y,i,i+s-1,i+2*s-1); i=i+2*s; } if(i+s<n) Merge(x,y,i,i+s-1,n-1); else for(int j=i;j<=n-1;j++) y[j]=x[j]; } void MergeSort(int *c,int n) { int *b=new int[n]; int s=1; while (s<n) { MergePass(c,b,s,n); s+=s; MergePass(b,c,s,n); s+=s; } } void mergerSort(int *b,int n) { clock_t start,finish; //定义时间 double totaltime; start=clock();// 开始时间 /* --------------算法操作------------*/ MergeSort(b,n); /* --------------算法操作------------*/ finish=clock(); if(n==10){ //n 是10 的时候输出排序结果 for(int v=0;v<n;v++) cout<<b[v]<<" "; }else { totaltime=(double)(finish-start)/CLOCKS_PER_SEC;//计算工作时间 cout<<"此程序的运行时间为:"<<totaltime<<"秒!"<<endl; } } void inc_sort(int *a,int size,int bucket_size){ //定义桶的数目，和桶排序的逻辑 KeyNode **bucket_table=(KeyNode **)malloc(bucket_size*sizeof(KeyNode *)); for(int i=0;i<bucket_size;i++){ bucket_table[i]=(KeyNode *)malloc(sizeof(KeyNode)); bucket_table[i]->key=0; //记录当前桶中的数据量 bucket_table[i]->next=NULL; } for(int j=0;j<size;j++){ KeyNode *node=(KeyNode *)malloc(sizeof(KeyNode)); node->key=a[j]; node->next=NULL; //映射函数计算桶号 int index=a[j]/10; //初始化P成为桶中数据链表的头指针 KeyNode *p=bucket_table[index]; //该桶中还没有数据 if(p->key==0){ bucket_table[index]->next=node; (bucket_table[index]->key)++; }else{ //链表结构的插入排序 while(p->next!=NULL&&p->next->key<=node->key) p=p->next; node->next=p->next; p->next=node; (bucket_table[index]->key)++; } } //打印结果 if(size==10||size==20){ for(int b=0;b<bucket_size;b++) for(KeyNode *k=bucket_table[b]->next; k!=NULL; k=k->next) cout<<k->key<<" "; cout<<endl; } } void barrelSort(int *b,int n) { clock_t start,finish; //定义时间 double totaltime; start=clock();// 开始时间 /* --------------算法操作------------*/ inc_sort(b,n,n);//定义n个桶 /* --------------算法操作------------*/ finish=clock(); totaltime=(double)(finish-start)/CLOCKS_PER_SEC;//计算工作时间 cout<<"此程序的运行时间为:"<<totaltime<<"秒!"<<endl; } void show() { cout<<"选择排序算法"<<endl; cout<<"1 插入排序"<<endl; cout<<"2 希尔排序"<<endl; cout<<"3 快速排序"<<endl; cout<<"4 冒泡排序"<<endl; cout<<"5 合并排序"<<endl; cout<<"6 桶排序 "<<endl; cout<<"0 退出 "<<endl; } void compare(int k,int *e, int n) { switch(k){ case 1: insertSort(e,n); break; case 2: sheerSort(e,n); break; case 3: fastSort(e,n); break; case 4: bubbleSort(e,n); break; case 5: mergerSort(e,n); break; case 6: barrelSort(e,n); break; } delete [] e; } /*——————————————————————————————————*/ void main() { /*-----------排序-----------------*/ int n;//问题规模 cout<<"输入随机空间大小 "<<endl; cin>>n; /*-----------产生自定义空间的随机数-----------------*/ srand((unsigned)time(NULL)); int *a=new int[n]; int s=n,m=n; cout<<n<<"个随机数是："; for (s=0;s<n;s++) { a[s]=(rand()%m)+1; if(n==10||n==20){ cout<<a[s]<<" "; } } cout<<endl; if(n==1000||n==10000||n==100000) { cout<<"各种算法排序后所要时间显示"<<endl; cout<<"直接插入排序："<<endl; //insertSort(a,n); cout<<"希尔排序："<<endl; //sheerSort(a,n); cout<<"快速排序："<<endl; fastSort(a,n); cout<<"冒泡排序："<<endl; bubbleSort(a,n); cout<<"归并排序："<<endl; mergerSort(a,n); cout<<"桶排序："<<endl; barrelSort(a,n