快速排序被廣泛認為它是解決一般問題的最佳排序算法，它比較適合解決大規模數據的排序。 原理思想：（從小到大） 快速排序首先選取一個“基准數”，通過基准數將大於它和小於它的數無序地放在基准數的兩邊 什麼叫無序？就是大於基准數的所有數只需要放在它的右邊，這些數之間不被要求為有序，同樣，小於基准數的數所有只需要放在它的左邊，不被要求有序 這樣就利用“基准數”對整個原始數列進行了分割成兩部分，然後通過遞歸，用上述同樣的方法選取一個基准數進行分割，直至整個數列被分割的各部分已不能再被分割 下面進行演示，基准數用定義一個變量 pivot 存放，每一部分的分割開始都是選擇low下標對應的數 這裡演示的就是代碼中 partition函數 的實現 開始：（假設low=0，high=6. 當前的low是紅色，high是綠色，pivot是藍色，被放置好在基准數兩邊的數用藍色字體表示） 原始數列a[7] 0 1 2 3 4 5 6 5 4 7 9 2 1 3 首先，選取基准數進行分割，選擇low下標當前的元素5為基准數，即pivot = 5 然後將 pivot 與 high 下標對應的數進行對比 如果 <= a[high]，則 low++ 如果 > a[high] ，則交換 a[low] 與 a[high] 結果如下： 第一次 0 1 2 3 4 5 6 3 4 7 9 2 1 5 從上圖可以看出，a[low] 與 a[high]已被交換 注意！ 在這個時候，因 pivot = 5 被交換到 high 的下標處 那麼接下來的比較就是將pivot與low下標當前的數進行對比 如果 >= a[low]，則 low++ 如果 < a[low] ，則交換 a[low] 與 a[high] 這裡是比low對應的數大，結果如下： 第二次 0 1 2 3 4 5 6 3 4 7 9 2 1 5 繼續使用pivot = 5 與 a[low] 進行對比 結果如下： 第三次 0 1 2 3 4 5 6 3 4 7 9 2 1 5 繼續使用 pivot = 5 與 a[low] 進行對比 這時候 pivot = 5比 a[low] 小，所以又進行a[low] 與 a[high]交換 結果如下： 第四次 0 1 2 3 4 5 6 3 4 5 9 2 1 7 注意！ 在這個時候，因pivot = 5被交換到low的下標處 那麼接下來的比較就是將pivot與high下標當前的數進行對比 如果 >= a[high]，則 high-- 如果 < a[high] ，則交換 a[low] 與 a[high] 結果如下： 第五次 0 1 2 3 4 5 6 3 4 5 9 2 1 7繼續使用 pivot = 5 與 a[high] 進行對比 同樣進行交換，結果如下： 第六次 0 1 2 3 4 5 6 3 4 1 9 2 5 7繼續使用 pivot = 5 與 a[low] 進行對比 結果如下：（low++） 第七次 0 1 2 3 4 5 6 3 4 1 9 2 5 7繼續使用 pivot = 5 與 a[low] 進行對比 結果如下： 第八次 0 1 2 3 4 5 6 3 4 1 5 2 9 7繼續使用 pivot = 5 與 a[high] 進行對比 結果如下：（high--） 第九次 0 1 2 3 4 5 6 3 4 1 5 2 9 7繼續使用 pivot = 5 與 a[high] 進行對比 結果如下：（最終結果low == high，橙色表示） 第九次 0 1 2 3 4 5 6 3 4 1 2 5 9 7最後由於 low++ 所以 low == high 到這裡，已經利用 基准數pivot = 5 把這個數列分為了兩部分（5 的左邊都是小於它的，右邊都是大於它的） 然後遞歸。用同樣的方法，對分割出來的兩部分用“基准數”繼續進行分割 快排函數代碼： [cpp] //快排函數 void sort(int *s, int low, int high) { int pivot; //if語句的判斷是結束遞歸的簡單情景，不能缺 if (low < high) { // partition 函數就是利用基准數進行分割的功能函數，這個函數是重點 pivot = partition(s, low, high); sort(s, pivot + 1, high); sort(s, low, pivot - 1); } } 什麼是遞歸的簡單情景？可以看看這裡 partition 函數代碼： [cpp] //這個函數就是上面演示的代碼實現 int partition(int *s, int low, int high) { int pivot; pivot = s[low]; while (low < high) { while (low < high && pivot <= s[high]) { high--; } www.2cto.com swap(&s[low], &s[high]); while (low < high && pivot >= s[low]) { low++; } swap(&s[high], &s[low]); } return low; }
