seven_kind_sorting.rar_4 3 2 1_排序综合

#include <iostream> # define maxsize 100 using namespace std; int part(int shu[],int low,int high) { shu[0]=shu[low]; int pivotkey=shu[0]; while(low<high) { while(low<high&&shu[high]>=pivotkey) --high; shu[low]=shu[high]; while(low<high&&shu[low]<=pivotkey) ++low; shu[high]=shu[low]; } shu[low]=shu[0]; return low; } int quicksort(int shu[],int low,int high)//快速排序 { if(low<high) { int pivotloc=part(shu,low,high); quicksort(shu,low,pivotloc-1); quicksort(shu,pivotloc+1,high); } return 0; } int insertsort(int shu[],int length)//插入排序 { int i,j; for(i=2;i<=length;i++) { if(shu[i]<shu[i-1]) { shu[0]=shu[i]; shu[i]=shu[i-1]; for(j=i-2;shu[0]<shu[j];j--) shu[j+1]=shu[j]; shu[j+1]=shu[0]; } return 0; } } int selectsort(int shu[],int length)//选择排序 { int i,j,temp; for(i=1;i<=length;i++) { for(j=i+1;j<=length;j++) { if(shu[j]<shu[i]) { temp=shu[j]; shu[j]=shu[i]; shu[i]=temp; } } } } int bubblesort(int shu[],int length)//冒泡排序 { int i,j,temp; for(i=1;i<length;i++) { for(j=1;j<length;j++) { if(shu[j]>shu[j+1]) { temp=shu[j]; shu[j]=shu[j+1]; shu[j+1]=temp; } } } return 0; } int heapadjust(int shu[],int s,int m) { int rc=shu[s],j; for(j=2*s;j<=m;j=j*2) { if(j<m&&shu[j]<shu[j+1]) j++; if(rc>=shu[j]) break; shu[s]=shu[j];s=j; } shu[s]=rc; return 0; } int heapsort(int shu[],int length)//堆排 { int i,temp; for(i=length/2;i>0;i--)//建立大顶锥 heapadjust(shu,i,length); for(i=length;i>1;i--) { temp=shu[i]; shu[i]=shu[1]; shu[1]=temp; heapadjust(shu,1,i-1); } return 0; } int merge_1(int shu[],int shu_1[],int i,int m,int n) { int j,k; for(j=m+1,k=i;i<=m&&j<=n;k++) { if(shu[j]<=shu[k]) shu_1[k]=shu[i++]; else shu_1[k]=shu[j++]; } if(i<=m) for(;i<=n;i++) {shu_1[k]=shu[i];k++;} if(j<=n) for(;j<=n;j++) { shu_1[k]=shu[j]; k++; } return 0; } int msort(int shu[],int shu_1[],int s,int t)//归并排序 { int shu_2[maxsize]; if(s==t) shu_1[s]=shu[s]; else { int m=(s+t)/2; msort(shu,shu_2,s,m); msort(shu,shu_2,m+1,t); merge_1(shu_2,shu_1,s,m,t); } } int maxbit(int data[],int n)//一下为基数排序 { int d=1; for(int i=0;i<n;i++) { int c=1; int p=data[i]; while(p/10) { p=p/10; c++; } if(c>d) d=c; } return d; } void RadixSort(int data[],int n) { int count[10],i; int tmp[10]; int d=maxbit(data,n); int r=1; for(i=0;i<d;i++) { for(i=0;i<10;i++)//装桶之前要先清桶 count[i]=0; for(i=0;i<n;i++) //记录每个桶的记录数 { int k=data[i]/r; int q=k%10; count[q]++; } for(i=1;i<10;i++)//计算位置 { count[i]+=count[i-1]; //cout<<count[i]<<" "; } for(int j=n-1;j>=0;j--) { int p=data[j]/r; int s=p%10; tmp[count[s]-1]=data[j]; count[s]--; //cout<<data[j]<<" "; } for(i=0;i<n;i++) { data[i]=tmp[i]; //cout<<tmp[i]<<" "; } // cout<<endl; r=r*10; } } int main() { int num,cate,shu[maxsize],shu_1[maxsize]; int i=1,j=1; int shengjiang; cout<<"请输入待排序元素的个数："<<endl; cin>>num; cout<<"请输入待排元素："<<endl; while(i<=num) { cin>>shu[i]; i++; } cout<<"请输入排序类型的序号:"<<endl; cout<<"1.快速排序2.插入排序3.选择排序4.冒泡排序5.堆排序6.归并排序7.基数排序"<<endl; cin>>cate; if(cate==1) quicksort(shu,1,num); else if(cate==2) insertsort(shu,num); else if(cate==3) selectsort(shu,num); else if(cate==4) bubblesort(shu,num); else if(cate=5) heapsort(shu,num); else if(cate==6) msort(shu,shu,1,num); else if(cate==7) RadixSort(shu,num); else cout<<"没有这种排序"<<endl; cout<<"请选择升序还是降序：1代表升序2代表降序"<<endl; cin>>shengjiang; if(shengjiang==1) while(j<=num) { cout<<shu[j]<<' '; j++; } else { j=num; while(j>0) { cout<<shu[j]<<' '; j--; } } cout<<endl; return 0; }