排序算法無疑是學習數據結構中的重點內容，本文將給出排序算法的匯總。 下面是具體的實現： [cpp] #include<stdio.h> #include<stdlib.h> #include<time.h> #define N 1000000 int 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; }
