c++實現的快速排序、堆排序、歸并排序等排序算法全集
#include<stdio.h>include<stdlib.h>
struct node { int key; }r[20];
struct rnode { int key; int point; };
main() { void print(struct node a[20],int n); int creat(); void shell(struct node a[20],int n); int hoare(struct node a[20],int l,int h); void quick1(struct node a[20],int n); void quick2(struct node a[20],int l,int h); void heap(struct node a[20],int i,int m); void heapsort(struct node a[20],int n); void merges(struct node a[20],struct node a2[20],int h1,int mid,int h2); void mergepass(struct node a[20],struct node a2[20],int l,int n); void mergesort(struct node a[20],int n); int yx(int m,int i); int radixsort(struct rnode a[20],int n); int num,l,h,c; struct rnode s[20]; c=1; while(c!=0) { printf(" 主菜單 \n"); printf(" 1 輸入關鍵字，以-9999表示結束。\n"); printf(" 2 希爾排序 \n"); printf(" 3 非遞歸的快速排序 \n"); printf(" 4 遞歸的快速排序 \n"); printf(" 5 堆排序 \n"); printf(" 6 歸并排序 \n"); printf(" 7 基數排序 \n"); printf(" 輸入選擇 (1--7,0表示結束): "); scanf("%d",&c); switch(c) { case 1:num=creat();print(r,num);break; case 2:shell(r,num);print(r,num);break; case 3:quick1(r,num);print(r,num);break; case 4:l=0;h=num-1;quick2(r,l,h); printf("output quick2sort result:\n"); print(r,num);break; case 5:heapsort(r,num);break; case 6:mergesort(r,num);print(r,num);break; case 7:radixsort(s,num); } } }//main end
void print(struct node a[20],int n) { int i; for(i=0;i<n;i++) printf("%5d",a[i ].key); printf("\n"); }//print end
int creat() { int i,n; n=0; printf("input keys"); scanf("%d",&i); while(i!=-9999) { r[n].key=i; n++; scanf("%d",&i); } return(n); }//creat end
void shell(struct node a[20],int n)//希爾排序 { int i,j,k; for(i=n;i>=1;i--) a[i].key=a[i-1].key; k=n/2; while(k>=1) { for(i=k+1;i<=n;i++) { a[0].key=a[i].key; j=i-k; while((a[j].key>a[0].key)&&(j>=0)) { a[j+k].key=a[j].key; j=j-k; } a[j+k]=a[0]; } k=k/2; } for(i=0;i<n;i++) a[i].key=a[i+1].key; printf("輸出希爾排序的結果:\n"); }//shell end
////////////////////快速排序///////////////////////////
int hoare(struct node a[20],int l,int h)//分區處理函數 { int i,j; struct node x; i=l; j=h; x.key=a[i].key; do { while((i<j)&&(a[j].key>=x.key)) j--; if(i<j) { a[i].key=a[j].key; i++; } while((i<j)&&(a[i].key<=x.key)) i++; if(i<j) { a[j].key=a[i].key; j--; } }while(i<j); a[i].key=x.key; return(i); }//hoare end
void quick1(struct node a[20],int n) { int i,l,h,tag,top; int s[20][2]; l=0;h=n-1;tag=1;top=0; do { while(l<h) { i=hoare(a,l,h); top++; s[top][0]=i+1; s[top][1]=h; h=h-1; } if(top==0) tag=0; else { l=s[top][0]; h=s[top][1]; top--; } }while(tag==1); printf("輸出非遞歸快速排序結果:\n"); }//quick end
void quick2(struct node a[20],int l,int h)//遞歸的快速排序 { int i; if(l<h) { i=hoare(a,l,h); quick2(a,l,i-1); quick2(a,i+1,h); } }//quick2 end
////////////////////快速排序結束////////////////////////
////////////////////堆排序函數//////////////////////////
void heap(struct node a[20],int i,int m)//調整堆的函數 { struct node x; int j; x.key=a[i].key; j=2i; while(j<=m) { if(j<m) if(a[j].key>a[j+1].key) j++; if(a[j].key<x.key) { a[i].key=a[j].key; i=j; j=2i; } else j=m+1; } a[i].key=x.key; }//heap end
void heapsort(struct node a[20],int n)//堆排序的主體函數 { int i,v; struct node x; for(i=n;i>0;i--) a[i].key=a[i-1].key; for(i=n/2;i>=1;i--) heap(a,i,n); printf("輸出堆排序結果:\n"); for(v=n;v>=2;v--) { printf("%5d",a[1].key); x.key=a[1].key; a[1].key=a[v].key; a[v].key=x.key; heap(a,1,v-1); } printf("%5d",a[1].key); for(i=0;i<n;i++) a[i].key=a[i+1].key; }//heapsort end
/////////////////堆排序函數結束///////////////////
//////////////////歸并函數////////////////////////
void merges(struct node a[20],struct node a2[20],int h1,int mid,int h2) //歸并排序的核心算法 { int i,j,k; i=h1;j=mid+1;k=h1-1; while((i<=mid)&&(j<=h2)) { k=k+1; if(a[i].key<=a[j].key) { a2[k].key=a[i].key; i++; } else { a2[k].key=a[j].key; j++; } } while(i<=mid) { k++; a2[k].key=a[i].key; i++; } while(j<=h2) { k++; a2[k].key=a[j].key; i++; } }//merges end
void mergepass(struct node a[20],struct node a2[20],int l,int n) //一趟歸并 { int j,i,h1,mid,h2; i=0; while((n-i)>=2l) { h1=i; mid=h1+l-1; h2=i+2l-1; merges(a,a2,h1,mid,h2); i=i+2*l; } if((n-i)<=l) for(j=i;j<=n;j++) a2[j].key=a[j].key; else { h1=i; mid=h1+l-1; h2=n-1; merges(a,a2,h1,mid,h2); } }//mergepass end
void mergesort(struct node a[20],int n) { int l; struct node a2[20]; l=1; while(l<n) { mergepass(a,a2,l,n); l=2l; mergepass(a2,a,l,n); l=2l; } printf("輸出歸并排序的結果:\n"); }//mergesort end
///////////////歸并函數結束///////////////
///////////////基數排序///////////////////
int yx(int m,int i)//分離關鍵字倒數第i位有效數字的算法 { int x; switch(i) { case 1:x=m%10;break; case 2:x=(m%100)/10;break; case 3:x=(m%1000)/100;break; case 4:x=(m%10000)/1000;break; } return(x); }//yx end
int radixsort(struct rnode a[20],int n) { int f[11],e[11],i,j,k,l,p,d,t; for(i=1;i<=n;i++) { a[i].key=r[i-1].key; a[i].point=i+1; } a[n].point=0; p=1; printf("輸出關鍵字有效位數 d\n"); scanf("%d",&d); printf("輸出基數排序的結果:\n"); for(i=1;i<=d;i++) { for(j=0;j<=10;j++) { f[j]=0; e[j]=0; } while(p!=0) { k=yx(a[p].key,i); if(f[k]==0) { f[k]=p; e[k]=p; } else { l=e[k]; a[l].point=p; e[k]=p; } p=a[p].point; } j=0; while(f[j]==0) j++; p=f[j];t=e[j]; while(j<10) { j++; while((j<10)&&(f[j]==0)) j++; if(f[j]!=0) { a[t].point=f[j]; t=e[j]; } } a[t].point=0; t=p; while(t!=0) { printf("%5d",a[t].key); t=a[t].point; } printf("\n"); } return(p); } </pre>