内部排序比较.docVIP

内部排序算法的性能分析 对起泡排序、直接插入排序、快速排序、希尔排序、简单选择排序、堆排序和2-路归并排序算法对同一整数数组排序，精确得到不同排序所需的时间，比较后可知先进的排序算法比简单的排序算法要快的多；特别是待排元素较大时（10000）更明显。 #includestdio.h #includestdlib.h #includetime.h #includemath.h #includestring.h #includewindows.h #pragma comment(lib,winmm.lib) #define TRUE 1 #define FALSE 0 #define SNUM 7 int comp[SNUM]={0},move[SNUM]={0}; void Insert(int a[],int n){//直接插入排序 int i,j,temp; for(i=1;in;i++){ comp[0]++; if(a[i]a[i-1]){ temp=a[i];move[0]++; for(j=i-1;j=0tempa[j];j--){ a[j+1]=a[j];move[0]++;comp[0]++; } a[j+1]=temp;move[0]++; } } } void Shell(int a[],int n){//希尔排序 int i,j,temp,dk; for(dk=n/2;dk0;dk=dk/2) for(i=dk;in;i++){ comp[1]++; if(a[i]a[i-dk]){ temp=a[i];move[1]++; for(j=i-dk;j=0tempa[j];j-=dk) {a[j+dk]=a[j];move[1]++;comp[0]++;} a[j+dk]=temp;move[1]++; } } } void Bubble(int a[],int n){ //冒泡排序 int temp,i,j; int NOSWAP; for(i=n-1;i0;--i){ NOSWAP=TRUE; for(j=0;ji;j++){ comp[2]++; if(a[j]a[j+1]){ temp=a[j];a[j]=a[j+1]; a[j+1]=temp;NOSWAP=FALSE; move[2]+=3; } } if(NOSWAP)break; } } void Quick(int a[],int low,int high){ //快速排序 int temp,L=low,H=high; if(lowhigh){ temp=a[low];move[3]++; //用区间的第1个记录作为基准 while(lowhigh){ while(lowhigha[high]=temp) {high--;comp[3]++;} a[low]=a[high];move[3]++; while(lowhigha[low]=temp) {low++;comp[3]++;} a[high]=a[low];move[3]++; } a[low]=temp; move[3]++; //low的值相当于pivotkey Quick(a,L,low-1);//对左区间递归排序 Quick(a,low+1,H);//对右区间递归排序 } } void SelectSort(int a[],int n){ //简单选择排序 int i,j,k,tmp; for(i=0;in-1;i++){ k=i; for(j=i+1;jn;j++){ comp[4]++; if(a[j]a[k])k=j; } if(i!=k){ tmp=a[i];a[i]=a[k]; a[k]=tmp;move[4]+=3; } } } void HeapAdjust(int a[],int s,int m){ //使H.r[s..m]成为一个大顶堆 int j,tmp; tmp=a[s]; move[5]++; for(j=2*s+1;j=m;j*=2){ //j为s的左孩子，所以j=2*s+1 comp[5]++; if(jma[j]a[j+1])++j; if(tmp=a[j]) break; a[s]=a[j];move[5]++; s=j; } a[s]=tmp; } void HeapSort(int a[],int n){