【算法】快速排序算法的编码和优化
生活随笔
收集整理的這篇文章主要介紹了
【算法】快速排序算法的编码和优化
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
?
參考資料
《算法（第4版）》????????? — — Robert Sedgewick， Kevin Wayne 《啊哈！ 算法》????????????? — — 啊哈磊 《數據結構（教材）》???? — — 嚴蔚敏，吳偉民 ? ?快速排序算法的編碼描述
?快排的基本思路
??
? 快速排序的基本思路是：?
如上圖所示， 數組 3 1 4 1 5 9 2 6 5 3?
通過第一趟排序被分成了2 1 1 和4 5 9 3 6 5 3兩個子數組，且對任意元素，左子數組總小于右子數組 通過不斷遞歸處理，最終得到 1 1 2 3 3 4 5 5 6?
這個有序的數組 ?快排的實現步驟
? 快排具體的實現步驟如下圖所示： ??
圖中的步驟3，4不難理解，這里就不多贅述，因為步驟3中的遞歸思想是大家比較熟悉的， 步驟4中的“組合”其實就只是個概念上的詞，因為所有的子數組本來就連接在一起，只要所有的遞歸結束了，整個數組就是有序的。 ?下面我就只講解1和2步驟， 而在1,2中，關鍵在于如何實現“劃分”
切分的關鍵點：?基準元素，?左游標和右游標
?劃分的過程有三個關鍵點：“基準元素”， “左游標” 和“右游標”。
?- 基準元素：它是將數組劃分為兩個子數組的過程中， 用于界定大小的值， 以它為判斷標準， 將小于它的數組元素“劃分”到一個“小數值數組”里， 而將大于它的數組元素“劃分”到一個“大數值數組”里面。這樣，我們就將數組分割為兩個子數組， 而其中一個子數組里的元素恒小于另一個子數組里的元素
- 左游標： 它一開始指向待分割數組最左側的數組元素。在排序過程中，它將向右移動
- 右游標： 它一開始指向待分割數組最右側的數組元素。在排序過程中，它將向左移動
?一趟切分的具體過程
?
? 切分的具體過程如圖所示。在下圖中，基準元素是v,?? 左游標是i, 右游標是j i一開始指向數組頭部元素的位置lo, 切分時向右移動， j一開始指向數組末端元素hi,隨后向左移動， 當左右游標相遇的時候，一趟切分就完成了。 ? 當然， 看到這里你可能很懵懂，你可能會問：- “基準元素v是怎么選的？”
- 游標i,j的移動的過程中發生了什么事情（比如元素交換）？，
- 為什么左右游標相遇時一趟切分就完成了？
?
? （作為入門，啊哈磊老師的《啊哈，算法》里的圖示還是很有趣的！ 這里向大家安利一下） ? 【注意】下面在優化中會講關于基準元素的選取的訣竅， 但在快排的基礎編碼里，我們只要記住把頭部元素當作基準元素就夠了（假設數組元素是隨機分布的） ? 左右游標掃描和元素交換 ? 在選取了基準元素之后， 切分就正式開始了。這時候，左右游標開始分別向右/左移動，它們遵循的規則分別是： ?- 左游標向右掃描， 跨過所有小于基準元素的數組元素, 直到遇到一個大于或等于基準元素的數組元素， 在那個位置停下。
- 右游標向左掃描， 跨過所有大于基準元素的數組元素, 直到遇到一個大于或等于基準元素的數組元素，在那個位置停下
?
? 1.首先，右游標j會向左跨過所有大于基準元素的元素， 所以士兵j向左跨過了板磚8和10， 然后當他遇到了“小于等于”基準元素6的元素5時候， “哎呀， 不能再前進了，在這里打住吧！”， 于是右游標就在5處停了下來， 2.然后， 士兵i（左游標）跨過了小于基準元素6的1和2，然后遇到了“大于等于”6的7，在7處停了下來。 3.? 停下來之后， 左右游標所指的數組元素交換了它們的值（兩個士兵交換了他們腳下的板磚） ? 下圖同上：?
游標掃描和元素交換的意義 ? 很明顯， 兩個游標士兵的“工作” 就是不斷靠近，并檢查有沒有小于（大于）規定要求（即基準元素6）的板磚（元素），一旦發現， 就“丟”到對面去， 而當他們相遇的時候， 大小關系嚴格的兩塊子數組也就分割出來了 ? 【注意】 1.要注意一點： 我們選取的基準元素和左游標最初指定的元素是相同的！ 那么就我們就會發現一個問題: 當左游標向右掃描的時候，第一個遇到的“大于或等于”的元素就是它本身， 那么問題來了： 需不需要停下來呢？ 當然根據邏輯思考可以得出這是不必要的，所以下面我會結合算法指出這一細節： 左游標向右掃描的時候其實忽略了它最初所指的位置——頭元素的比較 2. 必須等一個“士兵”（游標）先走完， 另一個“士兵”（游標）才能走，不能每人輪流走一步... ? 左右游標相遇 ? 承接上文， 這次眼看士兵i和士兵j就要相遇了！ 首先士兵j先走，當它遇到3的位置的時候，因為3“小于等于”6，所以士兵j就停下來了。再然后士兵i向右走，但因為他和士兵j“碰頭”了，所以士兵i只能無奈地“提前”在3停住了（如果沒和j碰面士兵i是能走到9的!） ? 所以這就是左右游標掃描相遇時候遵循的原則： 只相遇， 不交叉?
【注意】這里你可能會問： 在我們制定的規則里， 左游標先掃描和右游標先掃描有區別嗎？? （如果你這樣想的話就和我想到一塊去了...嘿嘿），因為就上圖而言,兩種情況下一趟排序中兩個游標相遇的位置是不同的（一般而言，除非相遇位置的下方的元素剛好和基準元素相同）：
- 如果右游標先掃描，左右游標相遇的位置應該是3上方（圖示）
- 但如果左游標先掃描， 左右游標相遇的位置卻是9上方
?
這時候我們發現整個數組的組成是這樣的： 大小居中的基準元素 + 小數值數組 + 大數值數組 所以我們只要把基準元素6和游標相遇元素3換一下， 不就可以變成： 小數值數組 + 大小居中的基準元素 +?? 大數值數組 了嗎？ 即 1 2 5 4 3 6 9 7 10 8?
? 如圖所示 ? ??
至此， 一趟排序結束， 回到中間的6已經處于有序狀態，只要再對左右兩邊的元素進行遞歸處理就可以了?總結一趟排序的過程
? OK，這里讓我們總結下一趟快速排序的四個過程： ??
? 一趟排序全過程圖示 ? （A - Z 字母排序， A最小， Z最大）?
?快速排序代碼展示
?具體的代碼
這是我們的輔助函數exchange: 用于交換任意兩個數組元素的位置： // 交換兩個數組元素 private static void exchange(int [] a , int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp; }?
? 這是切分函數partition， 它完成了一輪排序的主要工作，使得待分割數組以基準元素為界，分成了一個小數值數組和一個大數值數組 private static int partition (int[] a, int low, int high) {int i = low, j = high+1;?// i, j為左右掃描指針 PS： 思考下為什么j比i 多加一個1呢？int pivotkey = a[low];? // pivotkey 為選取的基準元素（頭元素）while(true) {?while (a[--j]>pivotkey) {?? if(j == low) break; }? // 右游標左移while(a[++i]<pivotkey) {?? if(i == high) break;? }? // 左游標右移if(i>=j) break;??? // 左右游標相遇時候停止， 所以跳出外部while循環else exchange(a,i, j) ;? // 左右游標未相遇時停止, 交換各自所指元素，循環繼續? ??}exchange(a, low, j); // 基準元素和游標相遇時所指元素交換，為最后一次交換return j;? // 一趟排序完成， 返回基準元素位置 }?
? 這是主體函數sort, 將partition遞歸處理 private static void sort (int [] a,? int low, int high) {if(high<= low) { return; } // 終止遞歸int j = partition(a, low, high);? // 調用partition進行切分sort(a,? low,? j-1);?? // 對上一輪排序(切分)時，基準元素左邊的子數組進行遞歸sort(a,? j+1,? high); // 對上一輪排序(切分)時，基準元素右邊的子數組進行遞歸 }?
?對切分函數partition的解讀
? 1. 直觀上看， partition由兩部分組成： 外部while循環和兩個并列的內部while循環。 ? 2. 內部While循環的作用是使得左右游標相互靠近 例如對： while (a[--j]>pivotkey) {? ...?? }先將右游標左移一位，然后判斷指向的數組元素和基準元素pivotkey比較大小， 如果該元素大于基準元素， 那么循環繼續，j再次減1，右游標再次左移一位...... （循環體可以看作是空的）
? 3.外部While循環的作用是不斷通過exchange使得“逆序”元素的互相交換， 不斷向左子數組小于右子數組的趨勢靠近，? 對 if(i>=j) break;?從i < j到 i == j 代表了“游標未相遇”到“游標相遇”的過度過程，此時跳出外部循環， 切分已接近完成，緊接著通過 exchange(a, low, j) 交換基準元素和相遇游標所指元素的位置， low是基準元素的位置（頭部元素）, j是當前兩個游標相遇的位置
? 4. 第一個內部while循環體里面的的? if(j == low) break；判斷其實是多余的，可以去除。 因為在 while (a[--j]>pivotkey) {?? if(j == low) break; }? // 右游標左移中，當隨著右游標左移，到j = low + 1的時候，有 a[--j] == pivotkey為true（兩者都是基準元素），自動跳出了while循環，所以就不需要在循環體里再判斷 j == low 了
? 5. 注意一個細節： j 比 i 多加了一個1，為什么？ 如下 int i = low, j = high+1結合下面兩個While循環中的判斷條件：
while (a[--j]>pivotkey) {? ...?? } while (a[++i]<pivotkey) {? ...? }?可知道， 左游標 i 第一次自增的時候， 跳過了對基準元素 a[low] 所執行的 a[low] < pivotkey判斷, 這是因為在我們當前的算法方案里，基準元素和左游標初始所指的元素是同一個，所以沒有執行a[low]>pivotke這個判斷的必要。所以跳過（ 一開始a[low] == pivotkey，如果執行判斷那么一開始就會跳出內While循環，這顯然不是我們希望看到的）
? 而相比之下，右游標卻必須要對它初始位置所指的元素執行a[++i]<pivotkey ， 所以 j 比 i 多加了一個 ? ? ?對主體函數sort的解讀
? 1. high<= low是判斷遞歸結束的條件 2. int j = partition(a, low, high);? 有兩種作用： 一是進行一輪切分， 二是取得上一輪的基準元素的最終位置j, 傳遞給另外兩個sort函數，通過另外兩個sort函數的調用 sort(a,? low,? j-1);?? sort(a,? j+1,? high);進行下一輪遞歸，設置j -1 和j + 1 是因為上一輪基準元素的位置已經是有序的了，不要再納入下一輪遞歸里
? 快速排序QuickSort類的全部代碼： public class QuickSort {// 交換兩個數組元素private static void exchange(int [] a , int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;}private static int partition (int[] a, int low, int high) {int i = low, j = high+1;????? // i, j為左右掃描指針 PS： 思考下為什么j比i 多加一個1呢？int pivotkey = a[low];? // pivotkey 為選取的基準元素（頭元素）while(true) {?while (a[--j]>pivotkey) {?? if(j == low) break; }? // 右游標左移while(a[++i]<pivotkey) {?? if(i == high) break;? }? // 左游標右移if(i>=j) break;??? // 左右游標相遇時候停止， 所以跳出外部while循環else exchange(a,i, j) ;? // 左右游標未相遇時停止, 交換各自所指元素，循環繼續? ??? }exchange(a, low, j); // 基準元素和游標相遇時所指元素交換，為最后一次交換return j;? // 一趟排序完成， 返回基準元素位置 ? }private static void sort (int [] a,? int low, int high) {if(high<= low) { return; } // 當high == low, 此時已是單元素子數組，自然有序， 故終止遞歸int j = partition(a, low, high);? // 調用partition進行切分sort(a,? low,? j-1);?? // 對上一輪排序(切分)時，基準元素左邊的子數組進行遞歸sort(a,? j+1,? high); // 對上一輪排序(切分)時，基準元素右邊的子數組進行遞歸 ? }public static void sort (int [] a){ //sort函數重載， 只向外暴露一個數組參數sort(a, 0, a.length - 1);} }?
? 測試代碼 public class Test {public static void main (String [] args) {int [] array = {4,1,5,9,2,6,5,6,1,8,0,7 };QuickSort.sort(array);for (int i = 0; i < array.length; i++) {System.out.print(array[i]);}} }?
結果： 01124556789?
?優化點一 —— 切換到插入排序
? 對于小數組而言， 快速排序比插入排序要慢， 所以在排序小數組時應該切換到插入排序。 只要把sort函數中的 if(high<= low) { return; }?
改成： if(high<= low + M) {? Insertion.sort(a,low, high) return; } // Insertion表示一個插入排序類?
就可以了，這樣的話，這條語句就具有了兩個功能： 1. 在適當時候終止遞歸 2. 當數組長度小于M的時候（high-low <= M）， 不進行快排，而進行插排 ? 轉換參數M的最佳值和系統是相關的，一般來說， 5到15間的任意值在多數情況下都能令人滿意 ? 例如， 將sort函數改成： ? private static void sort (int [] a,? int low, int high) {if(high<= low + 10) {? Insertion.sort(a,low, high) return; } // Insertion表示一個插入排序類int j = partition(a, low, high);? // 調用partition進行切分sort(a,? low,? j-1);?? // 對上一輪排序(切分)時，基準元素左邊的子數組進行遞歸sort(a,? j+1,? high); // 對上一輪排序(切分)時，基準元素右邊的子數組進行遞歸}?
?優化點二 —— 基準元素選取的隨機化
? 上面說過，基準元素的選取是任意的，但是不同的選取方式對排序性能的影響很大。 ? 在上面所有的快速排序的例子中，我們都是固定選取基準元素，這種操作做了一個假設性的前提：數組元素的分布是隨機的。而如果數組不是隨機的，而是有一定順序的，甚至在最壞的情況下:完全正序或完全逆序， 這個時候麻煩就來了：?快排所消耗的時間大大延長，完全達不到快排應有的效果。 ? 所以為了保證快排算法的隨機化，我們必須進行一些優化。 ? 下面介紹的方法有三種：?
當然來了，因為亂序函數的運行，這會增加一部分耗時，但這可能是值得的 2.通過隨機數保證取得的基準元素的隨機性 ? private static int getRandom (int []a, int low, int high) {int RdIndex = (int) (low + Math.random()* (high - low)); // 隨機取出其中一個數組元素的下標exchange(a, RdIndex, low);? // 將其和最左邊的元素互換return a[low]; ? }private static int partition (int[] a, int low, int high) {int i = low, j = high+1;????? // i, j為左右掃描指針 PS： 思考下為什么j比i 多加一個1呢？int pivotkey = getRandom (a, low, high); // 基準元素隨機化while(true) {?while (a[--j]>pivotkey) {?? if(j == low) break; }? // 右游標左移while(a[++i]<pivotkey) {?? if(i == high) break;? }? // 左游標右移if(i>=j) break;??? // 左右游標相遇時候停止， 所以跳出外部while循環else exchange(a,i, j) ;? // 左右游標未相遇時停止, 交換各自所指元素，循環繼續? ??? }exchange(a, low, j); // 基準元素和游標相遇時所指元素交換，為最后一次交換return j;? // 一趟排序完成， 返回基準元素位置}?
? 3.? 三數取中法（推薦） 一般認為， 當取得的基準元素是數組元素的中位數的時候，排序效果是最好的，但是要篩選出待排序數組的中位數的成本太高， 所以只能從待排序數組中選取一部分元素出來再取中位數， 經大量實驗顯示： 當篩選數組的長度為3時候，排序效果是比較好的， 所以由此發展出了三數取中法： ? 三數取中法： 分別取出數組的最左端元素，最右端元素和中間元素， 在這三個數中取出中位數，作為基準元素。 ? package mypackage;public class QuickSort {// 交換兩個數組元素private static void exchange(int [] a , int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;}// 選取左中右三個元素，求出中位數， 放入數組最左邊的a[low]中private static int selectMiddleOfThree(int[] a, int low, int high) {int middle = low + (high -? low)/2;? // 取得位于數組中間的元素middleif(a[low]>a[high])??? {? exchange(a, low, high);? //此時有 a[low] < a[high] ??? }if(a[middle]>a[high]){ exchange(a, middle, high); //此時有 a[low], a[middle] < a[high] ??? }if(a[middle]>a[low]) {exchange(a, middle, low); //此時有a[middle]< a[low] < a[high] ??? }return a[low];? // a[low]的值已經被換成三數中的中位數， 將其返回 ? }private static int partition (int[] a, int low, int high) {int i = low, j = high+1;????? // i, j為左右掃描指針 PS： 思考下為什么j比i 多加一個1呢？int pivotkey = selectMiddleOfThree( a, low, high);while(true) {?while (a[--j]>pivotkey) {?? if(j == low) break; }? // 右游標左移while(a[++i]<pivotkey) {?? if(i == high) break;? }? // 左游標右移if(i>=j) break;??? // 左右游標相遇時候停止， 所以跳出外部while循環else exchange(a,i, j) ;? // 左右游標未相遇時停止, 交換各自所指元素，循環繼續? ??? }exchange(a, low, j); // 基準元素和游標相遇時所指元素交換，為最后一次交換return j;? // 一趟排序完成， 返回基準元素位置 ? }private static void sort (int [] a,? int low, int high) {if(high<= low) { return; } // 當high == low, 此時已是單元素子數組，自然有序， 故終止遞歸int j = partition(a, low, high);? // 調用partition進行切分sort(a,? low,? j-1);?? // 對上一輪排序(切分)時，基準元素左邊的子數組進行遞歸sort(a,? j+1,? high); // 對上一輪排序(切分)時，基準元素右邊的子數組進行遞歸 ? }public static void sort (int [] a){ //sort函數重載， 只向外暴露一個數組參數sort(a, 0, a.length - 1);} }
?
? ?優化點三 —— 去除不必要的邊界檢查
? 我在上面說過：“ 第一個內部while循環體里面的的? if(j == low) break；判斷其實是多余的，可以去除”? （請把文章往上翻到標題—“對切分函數partition的解讀”中的第4點） ? 那么， 能不能把另外一個邊界檢查? if(i == high) break; 也去除呢？ 當然是不能直接去除的，但是我們可以通過一些技巧使得我們能夠去除它 ? 首先要理解的是 if(i == high) break;的作用： 防止 i 增加到超過數組的上界， 造成數組越界的錯誤。 那么按照同樣的思考方式，對于 while(a[++i]<pivotkey) {?? if(i == high) break;? }我們只要嘗試把這一作用交給a[++i]<pivotkey去完成， 不就可以把 if(i == high) break; 給去掉了嗎？
? 這里的技巧就是： 在排序前先把整個數組中最大的元素移到數組的最右邊，這樣的話， 就算左游標i增加（右移）到數組的最右端，a[++i]<pivotkey也會判定為false(數組最大值當然是大于或等于基準元素的)， 從而無法越界。 ? 代碼： public class QuickSort {// 交換兩個數組元素private static void exchange(int [] a , int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;}//將原數組里最大的元素移到最右邊， 構造“哨兵”private static void Max(int [] a) {int max = 0;?for(int i = 1; i<a.length;i++) {if(a[i]>a[max]) {max = i;}}exchange(a, max, a.length -1);}private static int partition (int[] a, int low, int high) {int i = low, j = high+1;????? // i, j為左右掃描指針 PS： 思考下為什么j比i 多加一個1呢？int pivotkey = a[low];? // pivotkey 為選取的基準元素（頭元素）while(true) {?while (a[--j]>pivotkey) {?? }? // 空的循環體while(a[++i]<pivotkey) {?? }? // 空的循環體if(i>=j) break;??? // 左右游標相遇時候停止， 所以跳出外部while循環else exchange(a,i, j) ;? // 左右游標未相遇時停止, 交換各自所指元素，循環繼續?}exchange(a, low, j); // 基準元素和游標相遇時所指元素交換，為最后一次交換return j;? // 一趟排序完成， 返回基準元素位置 ? }private static void sort (int [] a,? int low, int high) {if(high<= low) { return; } // 當high == low, 此時已是單元素子數組，自然有序， 故終止遞歸int j = partition(a, low, high);? // 調用partition進行切分sort(a,? low,? j-1);?? // 對上一輪排序(切分)時，基準元素左邊的子數組進行遞歸sort(a,? j+1,? high); // 對上一輪排序(切分)時，基準元素右邊的子數組進行遞歸 ? }public static void sort (int [] a){ //sort函數重載， 只向外暴露一個數組參數Max(a); // 將原數組里最大元素移到最右邊， 構造“哨兵”sort(a, 0, a.length - 1);} }?
? 如果看到這里對“哨兵”這個概念還不是很清楚的話，看看下面這張圖示： 《三種哨兵》 ??
關于哨兵三再說幾句： 在處理內部子數組的時候，右子數組中最左側的元素可以作為左子數組右邊界的哨兵（可能有點繞） ?優化點四 —— 三切分快排（針對大量重復元素）
? 普通的快速排序還有一個缺點， 那就是會交換一些相同的元素 ? 回憶一下我在前面提到的快排中對左右游標指定的規則：- 左游標向右掃描， 跨過所有小于基準元素的數組元素, 直到遇到一個大于或等于基準元素的數組元素， 在那個位置停下。
- 右游標向左掃描， 跨過所有大于基準元素的數組元素，直到遇到一個大于或等于基準元素的數組元素，在那個位置挺停下
?
? 所以由此人們研究出了三切分快排（三路劃分） ， 在左右游標的基礎上，再增加了一個游標，用于處理和基準元素相同的元素 ??
? 代碼如下： package mypackage;public class Quick3way {public static void exchange(int [] a , int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;}public static void sort (int [] a, int low, int high) {if(low>=high)? { return; }int lt = low, gt = high, i =low+1;int v = a[low];while(i<=gt) {int aValue = a[i];if(aValue>v) { exchange(a, i, gt--);? }else if(aValue<v) { exchange(a, i++, lt++); }else{ i++; }}sort(a, low, lt-1);sort(a, gt+1, high);}public static void sort (int [] a) {sort(a, 0, a.length - 1);} }?
? ? 切分軌跡： ? （A - Z 字母排序， A最小， Z最大）?
（不好意思，pdf書里的截圖實在太模糊了，所以我自己用手機照了一張）?
?
其實啊，我只是把你們喝咖啡的時間，都用來喝啤酒而已總結
以上是生活随笔為你收集整理的【算法】快速排序算法的编码和优化的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： iOS开发-Xcode入门ObjC程序
- 下一篇： 如何让编码更加的标准