快速排序[优化枢轴及不必要的交换]

采用三数取中，并用0下标元素存储枢轴。

1. //CodeBy Pnig0s1992  
2. #include <iostream>  
3. using namespace std;  
4.  
5.  
6. int Partition(int * L,int low,int high);  
7. void QuickSort(int * L,int low,int high);  
8.  
9. int main(int argc,char * argv[])  
10. {  
11.     int L[10]={0,50,10,90,30,70,40,80,60,20};  
12.     QuickSort(L,1,9);  
13.     for (int index=1;index<=9;index++)  
14.     {  
15.         cout<<L[index]<<endl;  
16.     }  
17.     system("pause");  
18.     return 0;  
19. }  
20.  
21. void QuickSort(int * L,int low,int high)  
22. {  
23.     int privot;  
24.     if(low<high)  
25.     {  
26.         privot = Partition(L,low,high);  
27.         QuickSort(L,1,privot-1);  
28.         QuickSort(L,privot+1,high);  
29.     }  
30. }  
31.  
32. int Partition(int * L,int low,int high)  
33. {  
34.     int privo;  
35.     int m = low+(high-low)/2;  
36.     if(L[high]<L[m])  
37.         swap(L[m],L[high]);  
38.     if(L[high]<L[low])  
39.         swap(L[low],L[high]);  
40.     if(L[m]>L[low])  
41.         swap(L[m],L[low]);  
42.  
43.     privo = L[low];  
44.     L[0] = privo;  
45.     while(low<high)  
46.     {  
47.         while (low<high&&L[high]>=privo)  
48.         {  
49.             high--;  
50.         }  
51.         L[low] = L[high];  
52.         //swap(L[low],L[high]);  
53.         while(low<high&&L[low]<=privo)  
54.         {  
55.             low++;  
56.         }  
57.         L[high] = L[low];  
58.         //swap(L[low],L[high]);  
59.     }  
60.     L[low] = L[0];  
61.     return low;  
62. }  

本文转hackfreer51CTO博客，原文链接：http://blog.51cto.com/pnig0s1992/795896，如需转载请自行联系原作者