算法:快速排序实现 & 定制比较函数

 1 #include<stdio.h>
 2 const static int NUM = 47; 
 3 
 4 int quick_sort(int *a, int start, int end){
 5     if (start >= end) 
 6         return 0;   
 7 
 8     int partition = a[start];   //分割点value, 设置为第一个点.最后patition点设置为这个点
 9     int i  = start; //开始点
10     int j  = end;   //结束点
11 
12     while(i<j){ //循环多处判断i<j, 结束时i=j
13         while(i<j && a[j] >= partition) //i可置换   
14             --j;
15         a[i] = a[j];
16 
17         while(i<j && a[i] <= partition) //j可置换
18             ++i;
19         a[j] = a[i];
20     }   
21     printf("i=%d j=%d\n", i, j); 
22 
23     a[i] = partition;   //以上循环结束, i==j, i处即为分割点
24     quick_sort(a, start, i-1);
25     quick_sort(a, i+1, end);
26     return 0;   
27 }
28 
29 void print(int *a, int start, int end){
30     for (int i = start; i <= end; ++i){
31         printf("%d ", a[i]);    
32     }   
33     printf("\n");
34 }
35 
36 int main(){
37     int a[NUM];  
38     for (int i=0;i<NUM;++i){
39         a[i] = i%10;
40     }   
41 
42     print(a, 0, NUM-1);
43     quick_sort(a, 0, NUM-1);
44     print(a, 0, NUM-1);
45     return 0;
46 }

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 const static int BUCKET = 4;
 4 
 5 void print(int *a, int start, int end){
 6     for (int i = start; i <= end; ++i){
 7         printf("%d ", a[i]);    
 8     }   
 9     printf("\n");
10 }
11 
12 int comp(const void *a, const void *b){
13     int va = *(int*)a;
14     int vb = *(int*)b;
15 
16     if (va%BUCKET > vb%BUCKET){
17         return 1;   
18     }   
19     else if (va%BUCKET < vb%BUCKET){
20         return -1;  
21     }   
22     return va - vb; 
23 }
24 
25 int main(){
26     int a[] = {3,1,9,5,4,6,2};  
27     int NUM = sizeof(a)/sizeof(int);
28     
29     print(a, 0, NUM-1);
30     qsort(a, NUM, sizeof(int), comp);
31     print(a, 0, NUM-1);
32     return 0;
33 }