在編程珠璣一書對快速排序講得較為透徹，最早的快排是單向的，慢慢演化成雙向的，也就是目前的版本。從此書能看到這種演化的必要性。我想在這里，對其原理搞懂了就不會忘了（^_^）。 ### 快速排序思想 1962年，由C.A.R.Hoare創造出來。該算法核心思想就一句話：“**排序數組時，將數組分成兩個小部分，然后對它們遞歸排序**”。然而采取什么樣的策略將數組分成兩個部分是關鍵，想想看，如果隨便將數組A分成A1和A2兩個小部分，即便分別將A1和A2排好序，那么A1和A2重新組合成A時仍然是無序的。所以，我們可以在數組中找一個值，稱為key值，我們在把數組A分解為A1和A2前先對A做一些處理，讓小于key值的元素都移到其左邊，所有大于key值的元素都移到其右邊。這樣遞歸排序A1和A2，數組A就排好了。 **舉例**?? 我們要排序的數組如下： | 55 | 41 | 59 | 26 | 53 | 58 | 97 | 93 | |-----|-----|-----|-----|-----|-----|-----|-----| 我們選取第一個元素作為key值，即55.（一般都是選取第一個元素）。假如我們有一種辦法可以將數組做一步預處理，讓小于key值的元素都位于其左邊，大于key值的元素都位于其右邊，預處理完數組如下： | 41 | 26 | 53 | 55 | 59 | 58 | 97 | 93 | |-----|-----|-----|-----|-----|-----|-----|-----| 這樣數組就被key值劃分成了兩段，A[0...2]小于key，A[4...7]大于key，可見key值本身已排好序，接下來對A[0...2]和A[4...7]分別進行遞歸排序，那么整個數組就排好序了。預處理做的工作再次澄清下：找一個key值，把key位放到某位置A[p]，使小于key值的元素都位于A[p]左邊，大于key值的元素都位于A[p]的右邊。到此，我們的快排模型就成型了。 ~~~ //s, u 代表待排序部分的下界和上界 void qsort(s, u){ //遞歸結束條件是待排序部分的元素個數小于2 if(s >= u) { return; } //此處進行預處理，預處理后key值位于位置p qsort(s, p-1); qsort(p+1, u); } ~~~ 接下來看如何做預處理。我們選取A[0]做為key值, p作為key值的位置。我們從A[1]開始遍歷后面的數組，用變量i指示目前的位置，每次找到小于key的值都與A[++p]交換。開始時p=0. | 55 | 41 | 59 | 26 | 53 | 58 | 97 | 93 | |-----|-----|-----|-----|-----|-----|-----|-----| i = 1，A[i]位置為41, 即A[i] < key, swap(++p , i)，即p = 1: | 55 | 41 | 59 | 26 | 53 | 58 | 97 | 93 | |-----|-----|-----|-----|-----|-----|-----|-----| i = 2，A[i]位置為59，A[i] > key，不做任何改變。 i = 3，A[i]位置為26，A[i] < key，swap(++p, i)， 即p = 2: | 55 | 41 | 26 | 59 | 53 | 58 | 97 | 93 | |-----|-----|-----|-----|-----|-----|-----|-----| i = 4，A[i]位置為53，A[i] < key，swap(++p, i)，p = 3: | 55 | 41 | 26 | 53 | 59 | 58 | 97 | 93 | |-----|-----|-----|-----|-----|-----|-----|-----| i = 5，A[i]位置為58，A[i] > key，不做任何改變。 i = 6，A[i]位置為97，A[i] > key，不做任何改變. i = 7，A[i]位置為93，A[i] > key，不做任何改變.結束循環。此時p為key的最終位置。還需一步把key值填入p位置。 最后swap(l, p)即把Key值放到最終位置上了。至于為什么要交換l,p的位置，可以另拿一組數據試一下：55，41，59，26，99，58，97，93。 ~~~ //l, u 代表待排序部分的下界和上界 void qsort(int l, int u){ //遞歸結束條件是待排序部分的元素個數小于2 if(l >= u) return; ?int p = l; for(int i = l+1; i <= u; i++) { if(A[i] < A[l]) swap(++p, i); } swap(l, p); qsort(l, p-1); qsort(p+1, u); } ~~~ 這就是第一代快速排序算法，正常情況下其復雜度為nlogn，但在考慮一種極端情況：n個相同元素組成的數組。在n-1次劃分中每次劃分都需要O(n)的時間，所以總的時間為O（n^2）。使用雙向劃分就可以避免這個問題。 ### 雙向劃分快速排序 ~~~ /*l, u 代表待排序部分的下界和上界*/ void qsort(int l, int u){ /*遞歸結束條件是待排序部分的元素個數小于2*/ if(l >= u) return; key = A[l] for(int i = l, j = u+1; i <= j; ) { do i++ while(i <= u && A[i] < key)); do j-- while(A[j] > key); if(i > j) break; swap(i, j); } swap(l, j); qsort(l, j-1); qsort(j+1, u); } ~~~ **轉載請注明了出處**：[http://blog.csdn.net/utimes/article/details/8762451](http://blog.csdn.net/utimes/article/details/8762451)