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

 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 }