常用排序算法的C语言实现.docx

常用排序算法的C语言实现 /QuickSort快速排序 /BubbleSort冒泡排序 /InsertSort插入排序 /ShellSort希尔排序 /MegeSort归并排序 /HeapSort堆排序/BucketSort桶排序/RadixSort基数排序#include#include/*快速排序*/void QuickSort(int* a, int p, int q) int k,m,n,tmp; if(pq) k=aq; for(m=p,n=p;mq;m+) if(amk) tmp=am; am=an; an=tmp; n+; aq=an; an=k; QuickSort(a,p,n-1); QuickSort(a,n+1,q); /*冒泡排序*/void BubbleSort(int*a ,int n) int i,j; int tmp; if(n2) return ; for(i=0;in;i+) for(j=0;jaj+1) tmp=aj; aj=aj+1; aj+1=tmp; /*插入排序*/void InsertSort(int* a, int n) int i,j,k; if(n2) return ; for(i=1;i=0;j-) if(kaj) aj+1=aj; else aj+1=k; break; if(j1) d=(d+1)/2; for(i=0;in-d;i+) if(ai+dai) tmp=ai; ai=ai+d; ai+d=tmp; /*堆排序*/static void HeapAdjust(int* a, int i, int n) int lc=2*i+1; int rc=2*i+2; int M=i; int tmp; if(i=(n/2-1) if(lcai) M=lc; if(rcaM) M=rc; if(i!=M) tmp=aM; aM=ai; ai=tmp; HeapAdjust(a,M,n); static void BuildHeap(int* a, int n) int i; for(i=(n/2-1);i=0;i-) HeapAdjust(a,i,n); void HeapSort(int*a,int n) int i,tp; BuildHeap(a,n); for(i=n-1;i=0;i-) tp=ai; ai=a0; a0=tp; HeapAdjust(a,0,i); PrintA(a,13); /*桶排序（桶排序是一个已知范围排序，这里假设范围为0-99）*/void BucketSort(int* a, int n) int b100=0;/使用10个桶分别表示0-9 int i,j; for(i=0;in;i+) bai+=1; for(i=0,j=0;i100;i+) if(bi!=0) while(bi) aj+=i; bi-=1; /*基数排序:注意内存泄露(Max_W表示的是所排序元素的最大的元素有多少位)*/void RadixSort(int* a, int n, int Max_w) typedef struct LIST int val; struct LIST *next; List; int i,j,d; List r10; List *p,*q; for(i=0;i10;i+) ri.val=0; ri.next=NULL; for(i=0;inext!=NULL) p=p-next; p-next=(List *)malloc(sizeof(struct LIST); p-next-val=ai; p-next-next=NULL; for(i=0,j=0;inext!=NULL) aj+=p-next-val; p=p-next; while(ri.next!=NULL)/回收内存 p=&ri; q=p; while(p-next!=NULL) q=p; p=p-next; if(p!=q) free(p); q-next=NULL; for(j=1,d=1;jMax_w;j+) d=d*10; for(i=0;inext!=NULL) p=p-next; p-next=(List *)malloc(sizeof(struct LIST); p-next-val=ai; p-next-next=NULL; for(i=0,j=0;inext!=NULL) aj+=p-next-val; p=p-next; while(ri.next!=NULL)/回收内存 p=&ri; q=p; while(p-next!=NULL) q=p; p=p-next; if(p!=q) free(p); q-next=NULL; /*归并排序*/static void mege_init(int* a, int st, int mi, int en) int n1=mi-st+1; int n2=en-mi; int i,j,k; int *lef=(int*)malloc(n1*sizeof(int); int *rig=(int*)malloc(n2*sizeof(int); if(lef=NULL|rig=NULL) return ; for(i=0;in1;i+) lefi=ai+st; for(i=0;in2;i+) rigi=ai+mi+1; i=0; j=0; k=st; while(in1&jn2) if(lefirigj) ak=lefi+; else ak=rigj+; k+; while(in1) ak+=lefi+; while(jn2) ak+=rigj+; free(lef); free(rig);void MegeSort(int* a, int st, int en) int r; if(sten) r=(st+en)/2; MegeSort(a,st,r); MegeSort(a,r+1,en); mege_init(a,st,r,en); 测试函数int main() int a=52,28,57,68,98,19,27,46,85,39,72; PrintA(a,sizeof(a)/sizeof(int); /QuickSort(a,0,sizeof(a)/sizeof(int); /BubbleSort(a,sizeof(a)/sizeof(int); /InsertSort(a,sizeof(a)/sizeof(int); /ShellSort(a,sizeof(a)/sizeof(int); /MegeSort(a,0,sizeof(a)/sizeof(int); /HeapS