大家一起来找茬——快速排序算法

cnjn

下面是我第一次写快速排序算法时写出的代码，其中有一个BUG;有兴趣的朋友可以试试排错。


虽然这段代码可以正常执行，但确实有一个bug哦

1. #include<stdio.h>
   
2. void quick_sort(int *num,int len){
   
3.         if(len<2) return;
   
4.         int center=num[(len%2+len)/2],i=0,j=len-1;
   
5.         while(1){
   
6.                 i=0;
   
7.                 j=len-1;
   
8.                 while(num[i]<center){
   
9.                         i++;
   
10.                 }
    
11.                 while(num[j]>center){
    
12.                         j--;
    
13.                 }
    
14.                 if(i<j){
    
15.                         int tmp=num[i];
    
16.                         num[i]=num[j];
    
17.                         num[j]=tmp;
    
18.                 }else{
    
19.                         int h=0;
    
20.                         while(h<len){
    
21.                                 if(num[h]==center){
    
22.                                         break;
    
23.                                 }
    
24.                                 h++;
    
25.                         }
    
26.                         quick_sort(num,h);
    
27.                         quick_sort(&num[h],len-h);
    
28.                         break;
    
29.                 }
    
30.         }
    
31. }
    
32. int main(){
    
33.         int num[]={0,6,5,3,1,2,4};
    
34.         for(int i=0;i<7;i++){
    
35.                 printf("%d ",num[i]);
    
36.         }
    
37.         puts("\n");
    
38.         quick_sort(num,sizeof(num)/sizeof(int));
    
39.         for(int i=0;i<7;i++){
    
40.                 printf("%d ",num[i]);
    
41.         }
    
42.         putchar('\n');
    
43. 
    
44. }
    

复制代码

另附上我修改后的代码：

1. #include<stdio.h>
   
2. void quick_sort(int *num,int len){
   
3.         if(len<2) return;
   
4.         int center=num[(len%2+len)/2],i=0,j=len-1;
   
5.         while(1){
   
6.                 while(num[i]<center) i++;
   
7.                 while(num[j]>center) j--;
   
8.                 if(i<j){
   
9.                         int tmp=num[i];
   
10.                         num[i]=num[j];
    
11.                         num[j]=tmp;
    
12.                         i++;
    
13.                         j--;
    
14.                 }else{
    
15.                         quick_sort(num,i);
    
16.                         quick_sort(&num[i],len-i);
    
17.                         break;
    
18.                 }
    
19.         }
    
20. }
    
21. int main(){
    
22.         int num[]={3,6,9,5,1,2,4};
    
23.         for(int i=0;i<7;i++) printf("%d ",num[i]);
    
24.         puts("\n");
    
25.         quick_sort(num,sizeof(num)/sizeof(int));
    
26.         for(int i=0;i<7;i++) printf("%d ",num[i]);
    
27.         putchar('\n');
    
28. 
    
29. }
    

复制代码