數據結構和演算法（九）：高級排序

06-03

數據結構和演算法（九）：高級排序

1、希爾排序

　　①、直接插入排序

　　②、希爾排序圖解

　　③、排序間隔選取

　　④、knuth間隔序列的希爾排序演算法實現

　　⑤、間隔為2h的希爾排序

2、快速排序

　　①、快速排序的基本思路

　　②、快速排序的演算法實現

　　③、快速排序圖示

　　④、快速排序完整代碼

　　⑤、優化分析

　　在Java數據結構和演算法（三）——冒泡、選擇、插入排序演算法中我們介紹了三種簡單的排序演算法，它們的時間複雜度大O表示法都是O(N2)，如果數據量少，我們還能忍受，但是數據量大，那麼這三種簡單的排序所需要的時間則是我們所不能接受的。接著我們在講解遞歸的時候，介紹了歸併排序，歸併排序需要O(NlogN)，這比簡單排序要快了很多，但是歸併排序有個缺點，它需要的空間是原始數組空間的兩倍，當我們需要排序的數據佔據了整個內存的一半以上的空間，那麼是不能使用歸併排序的。

　　本篇博客將介紹幾種高級的排序演算法：希爾排序和快速排序。

正文：

1、希爾排序

　　希爾排序是基於直接插入排序的，它在直接插入排序中增加了一個新特性，大大的提高了插入排序的執行效率。所以在講解希爾排序之前，我們先回顧一下直接插入排序。

　　①、直接插入排序

　　直接插入排序基本思想是每一步將一個待排序的記錄，插入到前面已經排好序的有序序列中去，直到插完所有元素為止。

package com.ys.sort; public class InsertSort { public static int[] sort(int[] array){ int j; //從下標為1的元素開始選擇合適的位置插入，因為下標為0的只有一個元素，默認是有序的 for(int i = 1 ; i < array.length ; i++){ int tmp = array[i];//記錄要插入的數據 j = i; while(j > 0 && tmp < array[j-1]){//從已經排序的序列最右邊的開始比較，找到比其小的數 array[j] = array[j-1];//向後挪動 j--; } array[j] = tmp;//存在比其小的數，插入 } return array; } }

　　我們可以分析一下這個直接插入排序，首先我們將需要插入的數放在一個臨時變數中，這也是一個標記符，標記符左邊的數是已經排好序的，標記符右邊的數是需要排序的。接著將標記的數和左邊排好序的數進行比較，假如比目標數大則將左邊排好序的數向右邊移動一位，直到找到比其小的位置進行插入。

　　這裡就存在一個效率問題了，如果一個很小的數在很靠近右邊的位置，比如上圖右邊待排序的數據 1 ，那麼想讓這個很小的數 1 插入到左邊排好序的位置，那麼左邊排好序的數據項都必須向右移動一位，這個步驟就是將近執行了N次複製，雖然不是每個數據項都必須移動N個位置，但是每個數據項平均移動了N/2次，總共就是N2/2，因此插入排序的效率是O(N2)。

那麼如果以某種方式不必一個一個移動中間所有的數據項，就能把較小的數據項移動到左邊，那麼這個演算法的執行效率會有很大的改進。

　　②、希爾排序圖解

　　希爾排序應運而生了，希爾排序通過加大插入排序中元素的間隔，並在這些有間隔的元素中進行插入排序，從而使數據項能夠大跨度的移動。當這些數據項排過一趟序後，希爾排序演算法減小數據項的間隔再進行排序，依次進行下去，最後間隔為1時，就是我們上面說的簡單的直接插入排序。

下圖顯示了增量為4時對包含10個數組元素進行排序的第一個步驟，首先對下標為 0,4,8 的元素進行排序，完成排序之後，演算法右移一步，對 1,5,9 號元素進行排序，依次類推，直到所有的元素完成一趟排序，也就是說間隔為4的元素都已經排列有序

　　當我們完成4-增量排序之後，在進行普通的插入排序，即1-增量排序，會比前面直接執行簡單插入排序要快很多。

　　③、排序間隔選取

　　對於10個元素，我們選取4的間隔，那麼100個數據，1000個數據，甚至更多的數據，我們應該怎麼選取間隔呢？

　　希爾的原稿中，他建議間隔選為N/2，也就是每一趟都將排序分為兩半，因此對於N=100的數組，逐漸減小的間隔序列為：50,25,12，6,3,1。這個方法的好處是不需要在開始排序前為找到初始序列的間隔而計算序列，只需要用2整除N。但是這已經被證明並不是最好的序列。

間隔序列中的數字互質是很重要的指標，也就是說，除了1，他們沒有公約數。這個約束條件使得每一趟排序更有可能保持前一趟排序已經排好的結果，而希爾最初以N/2的間隔的低效性就是沒有遵守這個準則。

所以一種希爾的變形方法是用2.2來整除每一個間隔，對於n=100的數組，會產生序列45，20，9,4,1。這比用2會整除會顯著的改善排序效果。

　　還有一種很常用的間隔序列：knuth 間隔序列 3h+1

但是無論是什麼間隔序列，最後必須滿足一個條件，就是逐漸減小的間隔最後一定要等於1，因此最後一趟排序一定是簡單的插入排序。

下面我們通過knuth間隔序列來實現希爾排序：

　　④、knuth間隔序列的希爾排序演算法實現

//希爾排序 knuth 間隔序列 3h+1public static void shellKnuthSort(int[] array){ System.out.println("原數組為"+Arrays.toString(array)); int step = 1 ; int len = array.length; while(step <= len/3){ step = step*3 + 1;//1,4,13,40...... } while(step > 0){ //分別對每個增量間隔進行排序 for(int i = step ; i < len ; i++){ int temp = array[i]; int j = i; while(j > step-1 && temp <= array[j-step]){ array[j] = array[j-step]; j -= step; } array[j] = temp; }//end for System.out.println("間隔為"+step+"的排序結果為"+Arrays.toString(array)); step = (step-1)/3; }//end while(step>0) System.out.println("最終排序："+Arrays.toString(array));}

　　測試結果：

public static void main(String[] args) { int[] array = {4,2,8,9,5,7,6,1,3,10}; shellKnuthSort(array);}

　　⑤、間隔為2h的希爾排序

//希爾排序間隔序列2hpublic static void shellSort(int[] array){ System.out.println("原數組為"+Arrays.toString(array)); int step; int len = array.length; for(step = len/2 ;step > 0 ; step /= 2){ //分別對每個增量間隔進行排序 for(int i = step ; i < array.length ; i++){ int j = i; int temp = array[j]; if(array[j] < array[j-step]){ while(j-step >=0 && temp < array[j-step]){ array[j] = array[j-step]; j -= step; } array[j] = temp; } } System.out.println("間隔為"+step+"的排序結果為"+Arrays.toString(array)); }}

　　測試結果：

2、快速排序

　　快速排序是對冒泡排序的一種改進，由C. A. R. Hoare在1962年提出的一種劃分交換排序，採用的是分治策略（一般與遞歸結合使用），以減少排序過程中的比較次數。

　　①、快速排序的基本思路

　　一、先通過第一趟排序，將數組原地劃分為兩部分，其中一部分的所有數據都小於另一部分的所有數據。原數組被劃分為2份

　　二、通過遞歸的處理，再對原數組分割的兩部分分別劃分為兩部分，同樣是使得其中一部分的所有數據都小於另一部分的所有數據。這個時候原數組被劃分為了4份

　　三、就1,2被劃分後的最小單元子數組來看，它們仍然是無序的，但是！它們所組成的原數組卻逐漸向有序的方向前進。

　　四、這樣不斷劃分到最後，數組就被劃分為多個由一個元素或多個相同元素組成的單元，這樣數組就有序了。

　　具體實例：

　　對於上圖的數組[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]

　　②、快速排序的演算法實現

　　假設被排序的無序區間為[A[i],......,A[j]]

一、基準元素選取：選擇其中的一個記錄的關鍵字 v 作為基準元素（控制關鍵字）;怎麼選取關鍵字？

　　二、劃分：通過基準元素 v 把無序區間 A[I]......A[j] 劃分為左右兩部分，使得左邊的各記錄的關鍵字都小於 v；右邊的各記錄的關鍵字都大於等於 v；（如何劃分？）

　　三、遞歸求解：重複上面的一、二步驟，分別對左邊和右邊兩部分遞歸進行快速排序。

　　四、組合：左、右兩部分均有序，那麼整個序列都有序。

　　上面的第三、四步不用多說，主要是第一步怎麼選取關鍵字，從而實現第二步的劃分？

　　劃分的過程涉及到三個關鍵字：「基準元素」、「左游標」、「右游標」

　　基準元素：它是將數組劃分為兩個子數組的過程中，用於界定大小的值，以它為判斷標準，將小於它的數組元素「劃分」到一個「小數值的數組」中，而將大於它的數組元素「劃分」到一個「大數值的數組」中，這樣，我們就將數組分割為兩個子數組，而其中一個子數組的元素恆小於另一個子數組裡的元素。

左游標：它一開始指向待分割數組最左側的數組元素，在排序的過程中，它將向右移動。

右游標：它一開始指向待分割數組最右側的數組元素，在排序的過程中，它將向左移動。

　　注意：上面描述的基準元素/右游標/左游標都是針對單趟排序過程的，也就是說，在整體排序過程的多趟排序中，各趟排序取得的基準元素/右游標/左游標一般都是不同的。

　　對於基準元素的選取，原則上是任意的。但是一般我們選取數組中第一個元素為基準元素（假設數組是隨機分布的）

③、快速排序圖示

　　上面表示的是一個無序數組，選取第一個元素 6 作為基準元素。左游標是 i 哨兵，右游標是 j 哨兵。然後左游標向左移動，右游標向右移動，它們遵循的規則如下：

　　一、左游標向右掃描， 跨過所有小於基準元素的數組元素, 直到遇到一個大於或等於基準元素的數組元素，在那個位置停下。

　　二、右游標向左掃描， 跨過所有大於基準元素的數組元素, 直到遇到一個小於或等於基準元素的數組元素，在那個位置停下。

　　第一步：哨兵 j 先開始出動。因為此處設置的基準數是最左邊的數，所以需要讓哨兵 j 先開始出動，哨兵 j 一步一步的向左挪動，直到找到一個小於 6 的元素停下來。接下來，哨兵 i 再一步一步的向右挪動，直到找到一個大於 6 的元素停下來。最後哨兵 i 停在了數字 7 面前，哨兵 j 停在了數字 5 面前。

　　到此，第一次交換結束，接著哨兵 j 繼續向左移動，它發現 4 比基準數 6 要小，那麼在數字4面前停下來。哨兵 i 也接著向右移動，然後在數字 9 面前停下來，然後哨兵 i 和哨兵 j 再次進行交換。

　　第二次交換結束，哨兵 j 繼續向左移動，然後在數字 3 面前停下來；哨兵 i 繼續向右移動，但是它發現和哨兵 j 相遇了。那麼此時說明探測結束，將數字 3 和基準數字 6 進行交換，如下：

　　到此，第一次探測真正結束，此時已基準點 6 為分界線，6 左邊的數組元素都小於等於6,6右邊的數組元素都大於等於6。

　　左邊序列為【3,1,2,5,4】,右邊序列為【9,7,10,8】。接著對於左邊序列而言，以數字 3 為基準元素，重複上面的探測操作，探測完畢之後的序列為【2,1,3,5,4】；對於右邊序列而言，以數字 9 位基準元素，也重複上面的探測操作。然後一步一步的劃分，最後排序完全結束。

通過這一步一步的分解，我們發現快速排序的每一輪操作就是將基準數字歸位，知道所有的數都歸位完成，排序就結束了。

　　④、快速排序完整代碼

package com.ys.high.sort; public class QuickSort { //數組array中下標為i和j位置的元素進行交換 private static void swap(int[] array , int i , int j){ int temp = array[i]; array[i] = array[j]; array[j] = temp; } private static void recQuickSort(int[] array,int left,int right){ if(right <= left){ return;//終止遞歸 }else{ int partition = partitionIt(array,left,right); recQuickSort(array,left,partition-1);// 對上一輪排序(切分)時，基準元素左邊的子數組進行遞歸 recQuickSort(array,partition+1,right);// 對上一輪排序(切分)時，基準元素右邊的子數組進行遞歸 } } private static int partitionIt(int[] array,int left,int right){ //為什麼 j加一個1，而i沒有加1,是因為下面的循環判斷是從--j和++i開始的. //而基準元素選的array[left],即第一個元素，所以左游標從第二個元素開始比較 int i = left; int j = right+1; int pivot = array[left];// pivot 為選取的基準元素（頭元素） while(true){ while(i<right && array[++i] < pivot){} while(j > 0 && array[--j] > pivot){} if(i >= j){// 左右游標相遇時候停止，所以跳出外部while循環 break; }else{ swap(array, i, j);// 左右游標未相遇時停止, 交換各自所指元素，循環繼續 } } swap(array, left, j);//基準元素和游標相遇時所指元素交換，為最後一次交換 return j;// 一趟排序完成，返回基準元素位置(注意這裡基準元素已經交換位置了) } public static void sort(int[] array){ recQuickSort(array, 0, array.length-1); } //測試 public static void main(String[] args) { //int[] array = {7,3,5,2,9,8,6,1,4,7}; int[] array = {9,9,8,7,6,5,4,3,2,1}; sort(array); for(int i : array){ System.out.print(i+" "); } //列印結果為：1 2 3 4 5 6 7 7 8 9 }}

　　⑤、優化分析

　　假設我們是對一個逆序數組進行排序，選取第一個元素作為基準點，即最大的元素是基準點，那麼第一次循環，左游標要執行到最右邊，而右游標執行一次，然後兩者進行交換。這也會劃分成很多的子數組。

　　那麼怎麼解決呢？理想狀態下，應該選擇被排序數組的中值數據作為基準，也就是說一半的數大於基準數，一般的數小於基準數，這樣會使得數組被劃分為兩個大小相等的子數組，對快速排序來說，擁有兩個大小相等的子數組是最優的情況。

　　三項取中劃分

為了找到一個數組中的中值數據，一般是取數組中第一個、中間的、最後一個，選擇這三個數中位於中間的數。

//取數組下標第一個數、中間的數、最後一個數的中間值private static int medianOf3(int[] array,int left,int right){ int center = (right-left)/2+left; if(array[left] > array[right]){ //得到 array[left] < array[right] swap(array, left, right); } if(array[center] > array[right]){ //得到 array[left] array[center] < array[right] swap(array, center, right); } if(array[center] > array[left]){ //得到 array[center] < array[left] < array[right] swap(array, center, left); } return array[left]; //array[left]的值已經被換成三數中的中位數，將其返回} private static int partitionIt(int[] array,int left,int right){ //為什麼 j加一個1，而i沒有加1,是因為下面的循環判斷是從--j和++i開始的. //而基準元素選的array[left],即第一個元素，所以左游標從第二個元素開始比較 int i = left; int j = right+1; int pivot = array[left];// pivot 為選取的基準元素（頭元素） int size = right - left + 1; if(size >= 3){ pivot = medianOf3(array, left, right); //數組範圍大於3，基準元素選擇中間值。 } while(true){ while(i<right && array[++i] < pivot){} while(j > 0 && array[--j] > pivot){} if(i >= j){// 左右游標相遇時候停止，所以跳出外部while循環 break; }else{ swap(array, i, j);// 左右游標未相遇時停止, 交換各自所指元素，循環繼續 } } swap(array, left, j);//基準元素和游標相遇時所指元素交換，為最後一次交換 return j;// 一趟排序完成，返回基準元素位置(注意這裡基準元素已經交換位置了)}

處理小劃分

如果使用三數據取中劃分方法，則必須遵循快速排序演算法不能執行三個或者少於三個的數據，如果大量的子數組都小於3個，那麼使用快速排序是比較耗時的。聯想到前面我們講過簡單的排序（冒泡、選擇、插入）。

　　當數組長度小於M的時候（high-low <= M），不進行快排，而進行插入排序。轉換參數M的最佳值和系統是相關的，一般來說， 5到15間的任意值在多數情況下都能令人滿意。

//插入排序private static void insertSort(int[] array){ for(int i = 1 ; i < array.length ; i++){ int temp = array[i]; int j = i; while(j > 0 && array[j-1] > temp){ array[j] = array[j-1]; j--; } array[j] = temp; }}

數據結構和演算法系列文章：

張曉康：數據結構與演算法（一）：簡介?

zhuanlan.zhihu.com張曉康：數據結構和演算法（二）：數組?