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

常用排序算法的C语言实现 //QuickSort快速排序 //BubbleSort冒泡排序 //InsertSort插入排序 //ShellSort希尔排序 //MegeSort归并排序 //HeapSort堆排序//BucketSort桶排序//RadixSort基数排序#includestdio.h#includestdlib.h/*快速排序*/voidQuickSort(int* a, int p, int q){intk,m,n,tmp;if(pq) { k=a[q];for(m=p,n=p;mq;m++) {if(a[m]k) {tmp=a[m];a[m]=a[n];a[n]=tmp;n++; } }a[q]=a[n];a[n]=k;QuickSort(a,p,n-1);QuickSort(a,n+1,q); }}/*冒泡排序*/voidBubbleSort(int*a ,int n){inti,j;inttmp;if(n2) return ;for(i=0;in;i++) {for(j=0;jn-i-1;j++) {if(a[j]a[j+1]) {tmp=a[j];a[j]=a[j+1];a[j+1]=tmp; } } }}/*插入排序*/voidInsertSort(int* a, int n){inti,j,k;if(n2) return ;for(i=1;in;i++) { k=a[i];for(j=i-1;j=0;j--) {if(ka[j]) {a[j+1]=a[j]; }else {a[j+1]=k;break; } }if(j0) {a[0]=k; } }}/*希尔排序*/voidShellSort(int* a, int n){int d=n;inti,tmp;while(d1) { d=(d+1)/2;for(i=0;in-d;i++) {if(a[i+d]a[i]) {tmp=a[i];a[i]=a[i+d];a[i+d]=tmp; } } }}/*堆排序*/static void HeapAdjust(int* a, inti, int n){intlc=2*i+1;intrc=2*i+2;int M=i;inttmp;if(i=(n/2-1)) {if(lcna[lc]a[i]) { M=lc; }if(rcna[rc]a[M]) { M=rc; }if(i!=M) {tmp=a[M];a[M]=a[i];a[i]=tmp;HeapAdjust(a,M,n); } }}static void BuildHeap(int* a, int n){inti;for(i=(n/2-1);i=0;i--) {HeapAdjust(a,i,n); }}voidHeapSort(int*a,int n){inti,tp;BuildHeap(a,n);for(i=n-1;i=0;i--) {tp=a[i];a[i]=a[0];a[0]=tp;HeapAdjust(a,0,i);PrintA(a,13); }}/*桶排序（桶排序是一个已知范围排序，这里假设范围为0-99）*/voidBucketSort(int* a, int n){int b[100]={0};//使用10个桶分别表示0-9inti,j;for(i=0;in;i++) {b[a[i]]+=1; }for(i=0,j=0;i100;i++) {if(b[i]!=0) {while(b[i]) {a[j++]=i;b[i]-=1; } } }}/*基数排序:注意内存泄露(Max_W表示的是所排序元素的最大的元素有多少位)*/voidRadixSort(int* a, int n, intMax_w){typedefstruct LIST{intval;struct LIST *next;}List;inti,j,