排序算法--排序算法汇总
排序算法无疑是学习数据结构中的重点内容，本文将给出排序算法的汇总。
下面是具体的实现：
#include<stdio.h>#include<stdlib.h>#include<time.h>#define N 1000000int Array[N];int Temp[N];//1、冒泡排序void BubbleSort(int a[],int n){ int i,j; int temp; int tag; for(i=n-1;i>0;i--){tag = 0; for(j=0;j<i;j++) if(a[j]>a[j+1]){ temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; tag=1; } if(tag==0) break; } }//2、简单插入排序void SimpleInsertSort(int a[],int n){ int i,j,k; int temp; for(i=1;i<n;i++){ for(j=0;j<i;j++) if(a[j]>a[i]){ k=j; break; } if(j==i) continue; temp=a[i]; for(j=i;j>k;j--) a[j]=a[j-1]; a[k]=temp; } }//3、希尔排序void ShellSort(int a[],int n,int d){ int h,i,j,k; int temp; do{ d=d/3+1; for(h=0;h<d;h++) for(i=h+d;i<n;i+=d){ for(j=h;j<i;j+=d) if(a[j]>a[i]){ k=j; break; } if(j==i) continue; temp=a[i]; for(j=i;j>k;j-=d) a[j]=a[j-d]; a[k]=temp; } }while(d>1); }//4、简单选择排序void SimpleSelectSort(int a[],int n){ int i,j,k; int temp; for(i=0;i<n;i++){ temp=a[i]; k=i; for(j=i+1;j<n;j++) if(a[j]<temp){ temp=a[j]; k=j; } if(k!=i){ temp=a[i]; a[i]=a[k]; a[k]=temp; } } }//5、堆排序void CreateHeap(int a[],int n){ int i,j; int temp; for(i=(n-2)/2;i>=0;i--){ j=2*i+1; while(j<n){ if(j+1<n&&a[j+1]>a[j]) j++; if(a[(j-1)/2]<a[j]){ temp=a[(j-1)/2]; a[(j-1)/2]=a[j]; a[j]=temp; } else break; j=2*j+1; } } }void HeapAdjust(int a[],int n){ int i=0; int j; int temp; while(i<n&&2*i+1<n){ j=2*i+1; if(j+1<n&&a[j+1]>a[j]) j++; if(a[i]<a[j]){ temp=a[i]; a[i]=a[j]; a[j]=temp; } else break; i=j; } }void HeapSort(int a[],int n){ int i; int temp; CreateHeap(a,n); for(i=n-1;i>0;i--){ temp=a[i]; a[i]=a[0]; a[0]=temp; HeapAdjust(a,i); } }//6、快速排序int partition(int a[],int low,int high){ int pivotKey=a[low]; while(low<high){ while(low<high&&pivotKey<=a[high]) high--; a[low]=a[high]; while(low<high&&a[low]<=pivotKey) low++; a[high]=a[low]; } a[low]=pivotKey; return low; }void QuickSort(int a[],int low,int high){ int pivotTag; if(low<high){ pivotTag=partition(a,low,high); QuickSort(a,low,pivotTag-1); QuickSort(a,pivotTag+1,high); } }//7、归并排序void Merge(int a[],int p,int q,int r){ int i,j; int *ptr=(int*)malloc((r-p+1)*sizeof(int)); int begin_1,end_1,begin_2,end_2; begin_1=p; end_1=q; begin_2=q+1; end_2=r; j=0; while(begin_1<=end_1&&begin_2<=end_2){ if(a[begin_1]<=a[begin_2]){ ptr[j]=a[begin_1]; begin_1++; } else{ ptr[j]=a[begin_2]; begin_2++; } j++; } while(begin_1<=end_1) ptr[j++]=a[begin_1++]; while(begin_2<=end_2) ptr[j++]=a[begin_2++]; for(i=0;i<r-p+1;i++) a[p+i]=ptr[i]; free(ptr); }void MergeSort(int a[],int first,int last){ int mid; if(first<last){ mid=(first+last)/2; MergeSort(a,first,mid); MergeSort(a,mid+1,last); Merge(a,first,mid,last); } }//8、基数排序(LSD)int MaxBit(int a[],int n){ int i; int d=1; int p=10; for(i=0;i<n;i++) while(a[i]>=p){ p*=10; ++d; } return d; }void RadixSort(int a[],int n){ int i,j,k; int radix=1; int d=MaxBit(a,n); int *ptr=(int*)malloc(n*sizeof(int)); int *count=(int*)malloc(10*sizeof(int)); for(i=1;i<=d;i++){ for(j=0;j<10;j++) count[j]=0; for(j=0;j<n;j++){ k=(a[j]/radix)%10; count[k]++; } for(j=1;j<10;j++) count[j]=count[j-1]+count[j]; for(j=n-1;j>=0;j--){ k=(a[j]/radix)%10; count[k]--; ptr[count[k]]=a[j]; } for(j=0;j<n;j++) a[j]=ptr[j]; radix*=10; } free(ptr); free(count); }int main(void){ int i; int index; clock_t first,second; for(i=0;i<N;i++) Array[i]=rand()%N; /*printf("原始数据为：\n"); for(i=0;i<N;i++) printf("%d\t",Array[i]); printf("\n");*/ while(1){ for(i=0;i<N;i++) Temp[i]=Array[i]; printf("请输入排序方法：\n"); printf("1---冒泡排序\n"); printf("2---简单插入排序\n"); printf("3---希尔排序\n"); printf("4---简单选择排序\n"); printf("5---堆排序\n"); printf("6---快速排序\n"); printf("7---归并排序\n"); printf("8---基数排序\n"); scanf("%d",&index); if(index<1||index>8) break; first=clock(); switch(index){ case 1: BubbleSort(Temp,N); break; case 2: SimpleInsertSort(Temp,N); break; case 3: ShellSort(Temp,N,10); break; case 4: SimpleSelectSort(Temp,N); break; case 5: HeapSort(Temp,N); break; case 6: QuickSort(Temp,0,N-1); break; case 7: MergeSort(Temp,0,N-1); break; default: RadixSort(Temp,N); } second=clock(); /*printf("排序后数据为：\n"); for(i=0;i<N;i++) printf("%d\t",Temp[i]);*/ printf("排序用时：%f秒\n\n",(double)(second-first)/CLOCKS_PER_SEC); } return 0; }