對快速排序的理解以及相關c++代碼

快速排序：在一組數據中，可以將左邊的數字當作樞軸（右邊也可以），接下來要做的就是，先從右邊找到比樞軸小的數，

再從左邊找到比樞軸大的數，接著將這兩個數進行交換，重覆上述步驟找出所有符合條件的數進行交換，

最後將樞軸放到比樞軸大的數與比樞軸小的數之間。之所以要從右邊開始找，並且找到比樞軸小的數是因為交換後小的數就在樞軸的左邊了。

下麵舉個比較特殊的例子希望能增加理解。

先從右往左找到比1小的第一個數字為0，此時的索引位置j=8，再從左往右找到比1大的第一個數字為9，此時的索引位置i=1，此時交換0和9，

繼續下一次重覆任務

先從右往左找到比1小的第一個數字為0，此時的索引位置,j=1，而從左往右找到比1大的第一個數字8此時的索引i=2，很明顯i>j，這是不允許的，

所以這時候就可以讓所選的樞軸1與j位置上的值交換（也就是把樞軸放到兩組數字中間）

先看1左邊的情況此時就一個數字1已經排好，

再看右邊的情況，從j+1的位置開始到最後，且以j+1的位置為樞軸，

從右邊找比8小的第一個數字為4，索引j=9，從左邊找比8大的第一個數字為9，索引i=8，交換4和9

按照上述邏輯繼續

8的左邊

從右往左找比4小的數字，從左往右找比4大的數字，並交換

繼續

繼續

8的左邊又被4分成兩段

8的右邊

4的左邊

4的右邊

這一次同樣以左邊為樞軸，從右邊找到5，左邊會一直找知道找到5所在的位置此時j=i

跳出迴圈直接把7與j的位置交換，讓樞紐7將這3個數分開，實際上7的右邊沒有值了

只需考慮7的左邊

所以最終就排好了

以下是c++帶模版的快速排序代碼

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 template<class T>
 6 void QuickSort(T *q, int left, int right);
 7 
 8 int main()
 9 {
10     int a[]={1,9,8,5,6,7,3,2,0,4};
11     QuickSort(a, 0, 9);
12     for(int i=0; i<10; i++)
13         cout << a[i] << endl;
14     return 0;
15 }
16 
17 template<class T>
18 void QuickSort(T *q, const int left, const int right)
19 {
20     if(left<right)
21     {
22         int i=left, j=right;
23         int temp = q[left];
24         while(i<j)
25         {
26             while(q[j]>=temp && i<j)
27             {
28                 j--;
29             }
30             while(q[i]<=temp && i<j)
31             {
32                 i++;
33             }
34             swap(q[i],q[j]);
35         }
36         swap(q[left], q[j]);
37         QuickSort(q, left, j-1);
38         QuickSort(q, j+1, right);
39     }
40 }