排序算法分析和总结.docxVIP

本部分实现各种排序算法以下以为 int 排序为例typedef int DateType; 直接插入排序 void insert_sort(DataType* arr,unsigned len,int (*comp)(DataType,DataType)) { int i,j,k; DataType tmp; for(i=1;i(int)len;++i) { for(j=i-1;j=0comp(arr[i],arr[j]);--j); tmp=arr[i]; for(k=i;kj+1;--k) arr[k]=arr[k-1]; arr[j+1]=tmp; } } 谢尔排序 void insert_sort1(DataType* arr,unsigned len,int (*comp)(DataType,DataType),unsigned span) { int i,j,k; DataType tmp; for(i=span;i(int)len;i+=span) { for(j=i-span;j=0comp(arr[i],arr[j]);j-=span); tmp=arr[i]; for(k=i;kj+(int)span;k-=(int)span) arr[k]=arr[k-span]; arr[j+span]=tmp; } } void shell_sort(DataType* arr,unsigned len,int (*comp)(DataType,DataType)) { #define D 2 int span=len/D; while(span) { int i; for(i=0;ispan;++i) insert_sort1(arr+i,len-i,comp,span); span/=2; } } 选择排序 unsigned select(DataType* arr,unsigned len,int (*comp)(DataType,DataType)) { unsigned i,min=0; for(i=1;ilen;++i) if(comp(arr[i],arr[min])) min=i; return min; } void select_sort(DataType* arr,unsigned len,int (*comp)(DataType,DataType)) { unsigned i; for(i=0;ilen;++i) { unsigned min=select(arr+i,len-i,comp)+i; swap_by_address(arr+i,arr+min); } } 堆排序 void make_heap(DataType* arr,unsigned len,int (*comp)(DataType,DataType)) { int i,cur; for(i=1;i(int)len;++i) { cur=i; while(comp(arr[(cur-1)/2],arr[cur])) { swap_by_address(arr+cur,arr+(cur-1)/2); cur=(cur-1)/2; } } } void sort_heap(DataType* arr,unsigned len,int (*comp)(DataType,DataType)) { int i; int cur,left,right; for(i=(int)len-1;i0;--i) { swap_by_address(arr,arr+i); cur=0; left=1; right=2; while(righticomp(arr[cur],arr[right])||lefticomp(arr[cur],arr[left])) { if(righticomp(arr[left],arr[right])) { } else { } swap_by_address(arr+cur,arr+right); cur=right; swap_by_address(arr+cur,arr+left); cur=left; left=2*cur+1; right=2*cur+2; } } } 冒泡排序 void bubble_sort(DataType* arr,unsigned len,int (*comp)(DataType,DataType)) { unsigned i,j; int flag; if(len=1) return ; for(i=0;ilen-1;++i) { flag=1; for(j=0;jlen-1-i;++j) if(comp(arr[j+1],arr[j])) { } if(flag) swap_b