快排

[cpp] view plaincopy

1. void quicksort(int num[],int start,int end)  
2. {  
3.     int key=num[start];  
4.     int prev = start;  
5.     int last = end;  
6.       
7.         //结束条件必不可少，否则将会进入死循环。  
8.     if(prev >= last)  
9.     {  
10.         return;  
11.     }  
12.   
13.     while(prev < last)  
14.     {  
15.         while(prev < last)  
16.         {  
17.             if(num[last] < key)  
18.             {  
19.                 num[prev]=num[last];  
20.                     ++prev;  
21.                            //当最后一个元素被写入到pre位置，循环应结束，pre后面的元素还没准备好         
22.                            break;  
23.                            //last此时还不能--，因为还没有将其覆盖。       
24.                      }  
25.              --last;  
26.         }  
27.   
28.         while(prev < last)  
29.         {  
30.             if(num[prev] > key)  
31.             {  
32.                 num[last]=num[prev];  
33.                 --last;  
34.                 break;  
35.             }  
36.             ++prev;  
37.         }  
38.     }  
39.   
40.     num[last] = key;  
41.       
42.     quicksort(num,start,last-1);  
43.     quicksort(num,last+1,end);  
44. }