【演算法】希爾排序 （ 插入排序3.0版本已經發布，是否更新？ (￣▽￣") ）

【參考資料】

《演算法（第4版）》 — — Robert Sedgewick， Kevin Wayne

在本篇筆記里，我從簡單的插入排序，到希爾排序，中間的一系列演算法，看起來就像是插入排序的「發展史」一般。這些點分別是：

• 直接插入排序（插入排序1.0版本）
• 基於插入排序的簡單優化（插入排序1.1和1.2版本）
• 折半插入排序（插入排序2.0版本）
• 希爾排序（插入排序3.0版本）

直接插入排序（插入排序1.0）

直接插入排序的概念

將一個數組元素插入到已經有序的序列中， 並使得比它大的元素全部右移一位，如此對所有元素處理的排序方式， 叫做直接插入排序。

（文章的排序默認是左小右大的順序）

單個元素的插入過程

對待插入元素來說， 它的左邊是一堆已經有序但未來可能發生位置變動（右移）的元素。

這兩點很重要： 已經有序和位置變動。

• 待排序元素左邊序列已經有序， 這是正確插入的基礎， 只有在這個前提下， 待排序元素才能在從左到右的比較和交換中插入正確的位置。
• 待排序元素的插入需要騰出空間， 這就需要使已有序序列中比它大的元素全部右移一位。

（下圖中顯示的是a[0]<a[4]<a[1]的情況）

上面的圖示範告訴我們要做兩件事： 「將元素放入適當位置」，「將有序序列中大於元素的部分全部右移一位」， 具體應該怎麼做呢？

我們是這樣做的：

1. 和相鄰的左邊元素的值比較大小
2. 如果左邊元素大於待排序元素，則交換兩者的值，左邊元素的值「右移」一位。
3. 如果左邊元素小於等於待排序元素，說明已經插入到「合適位置」了，一趟插入結束。

單個元素插入結束後，原來的有序序列的長度增加了一位， 當這個長度不斷增長直到覆蓋整個數組時，直接插入排序就完成了。

直接插入排序的代碼

我們一般用兩個嵌套的for循環來處理上面的邏輯， 在外部for循環中，設置變數 i 控制當前待插入元素的下標的移動；在內部for循環中，設置變數j用於控制待插入的值的比較和交換（左移到合適位置）

代碼如下：

/** * @Author: HuWan Peng * @Date Created in 23:16 2017/12/1 */public class InsertSort { /** * @description: 交換a[i]和a[j]的值 */ private static void exch (int []a,int i,int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } /** * @description: 插入排序 */ public static void sort (int []a) { int N = a.length; for(int i=1;i<N;i++){ for(int j=i;j>0&&a[j]<a[j-1];j--){ exch(a,j,j-1); } } }}

測試：

public class Test { public static void main (String args[]){ int [] a = {1,6,3,2,9,7,8,1,5,0}; InsertSort.sort(a); for(int i=0;i<a.length;i++){ System.out.println(a[i]); } }}

直接插入排序軌跡

時間複雜度

對於隨機排列的長度為N的值不重複的數組

最好情況下： 數組是完全有序的，那麼這個時候，每插入一個元素的時候，只要和前一個元素做比較就可以了，而且不需要交換。總共： 比較次數為N-1, 交換次數為0。時間複雜度為O(N)

最壞情況下： 數組是完全逆序的，插入下標為N的元素的時候， 要做N次比較和N次交換。例如對{5,4,3,2,1}。插入下標為1的4時候，4要和5比較和交換，數組變成{4,5,3,2,1}；這時到下標為2的3插入，3要和4,5比較和交換。 所以，總的比較、交換次數是1+2+3...+(N-1) = N(N-1)/2≈ (N^2) / 2，時間複雜度為O(N^2)

平均情況： 需要(N^2) / 4次比較和(N^2) / 4次交換，時間複雜度為O(N^2)

對插入排序簡單優化（插入排序1.1版本）

在排序中，有兩項重要的任務，分別是「條件判斷」和「元素移動」。因此，我們優化插排的著眼點也在於次，如何「減少條件判斷」和「減少元素移動」，從而優化插排的性能

優化點一： 去除內循環中j>0的判斷條件

先來看看我們的內循環的判斷條件

for(int j=i;j>0&&a[j]<a[j-1];j--){ exch(a,j,j-1);}

原因

j>0的判斷是為了防止j不斷自減的過程中到達a[-1]導致數組越界的錯誤。

更直接，具體一點說， 這個可能發生的錯誤是針對j>0後面的a[j]<a[j-1]這個表達式的。（就為了防止a[0]<a[-1]的發生）

思路

基於這一點，去除j>0判斷條件的思路是： 只要a[j]<a[j-1]能「主動防禦」數組越界的錯誤，例如在j=1這個臨界點變為false跳出循環， 我們不就不需要加j>0這個條件判斷了嗎？

方法

基於上面的思路，我們的方法是：

在排序開始前將數組裡最小的元素移動到數組的最左邊即a[0]。這樣，當j減小到1的時候，無論a[1]是數組中任何一個元素， 對 a[1]<a[0]都是false ! 循環自動跳出，這樣，就算沒有j>0的保護， 我們的a[j]<a[j-1]也是安全的！ 於是我們就可以把j>0去除了

代碼如下：

/** * @Author: HuWan Peng * @Date Created in 23:16 2017/12/1 */public class InsertSort { /** * @description: 交換a[i]和a[j]的值 */ private static void exch (int []a,int i,int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } /** * @description: 將數組a中最小的元素移到最左邊即a[0]; */ private static void moveMinLeft (int []a) { int min=0; for (int i=0;i<a.length;i++) { if(a[i]<a[min]){ min = i; } } exch(a,0,min); } /** * @description: 插入排序 */ public static void sort (int []a) { moveMinLeft(a); int N = a.length; for(int i=1;i<N;i++){ for(int j=i;a[j]<a[j-1];j--){ // j<0的條件已經去除 exch(a,j,j-1); } } }}

優化點二：避免交換，減少移動（元素）

在原始的插入排序中，我使用了元素交換的方法exch：

private static void exch (int []a,int i,int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; }

這會在待插入值左移的過程中，每移一位， 造成兩次的元素移動：a[i] = a[j];和 a[j] = a[i];

但實際上，我們可以實現插入值左移一位時， 只移動一次元素的操作：

我們可以先用一個臨時變數保存待插入的值，將「插入」的操作留給最後一步（4），這樣，在忽略最後一步的情況下，我們的確把數組元素的移動次數減少了一半！

代碼如下：

/** * @Author: HuWan Peng * @Date Created in 23:16 2017/12/1 */public class InsertSort { /** * @description: 不用exch的插入排序 */ public static void sort (int []a) { int N = a.length; for(int i=1;i<N;i++){ int t = a[i]; int j = i; while (j>0&&t<a[j-1]) { a[j] = a[j-1]; j--; } a[j] = t; } }}

折半插入排序（插入排序2.0）

雖然上面我們做了減少元素移動量的優化， 元素的移動量已經被減至最低了，在這一部分已經「沒有油水可以壓榨了」，如果想要進一步「削減開支」的話，就要從另一方面——「元素比較」入手啦

如下圖所示，我們要把3插入到0 1 2 4 5 6 7 8 9中的話，總共要做8次a[j]<a[j-1]的比較，這種比較操作量感覺有點昂貴，有什麼減少這個比較量的方法嗎？

讓我們思考下已有的條件和要解決的問題： 有序序列， 插入元素到合適位置。

等等！！ 似乎這讓我們想起了什麼。

是二分法！ 這個需求簡直就是為二分法私人定製的，因為二分法最擅長處理的情景，就是：在一個有序數組中找到目標元素，或者確認該元素並不存在。在這種情景需求下，二分法顯得相當簡潔高效。我們的任務是在「在有序數組中尋找一個值的合適位置」， 這和二分法的「主體業務」很類似，嗯，就決定是它了！

和二分法相結合的插入排序， 叫做折半插入排序

二分法的思想以及高效的原因

二分法查找：設置一個循環，不斷將數組的中間值（mid）和被查找的值比較，如果被查找的值等於a[mid],就返回mid;

否則，就將查找範圍縮小一半。如果被查找的值小於a[mid], 就繼續在左半邊查找;如果被查找的值大於a[mid], 就繼續在右半邊查找。

直到查找到該值或者查找範圍為空時， 查找結束。

如下圖所示：

（注意：前提是數組有序！）

更準確地說，折半插入排序的場景類似於二分法中的未命中查找（如上圖所示）

通過二分法查找插入位置時的軌跡

如果我們把二分查找的思想運用到插入排序中去就可以把原來需要8次的比較減少至3次！

未使用二分法： 8次比較使用二分法： 3次比較

這個差距隨著數組規模的擴大會越發劇烈。

我們的目標是： 在a[0]到a[9]中查找數值3的插入位置。

第一輪二分

首先取中間值：

mid = (0 + 9)/2 = 4; 又因為a[4] = 5 > 3, 結合數組有序性可知:

數值3插入的目標位置一定在a[0]到a[4]之間（一定不在a[5]到a[10]之間）， 於是將查找範圍縮小一半，下一輪在a[0]到a[4]間查找

第二輪二分

取得中間值： mid = (0 + 4)/2 =2; 因為a[2] = 2< 3, 數值3插入的目標位置一定在a[3]到a[4]之間（一定不在a[0]到a[2]之間）。 於是將查找範圍縮小一半，下一輪在a[3]到a[4]間查找

第三輪二分

取中間值： mid = (3 + 4)/2 = 3, 因為a[3] = 4 >3, 所以a[3]就是最終插入的位置。

找到插入位置之後， 將插入位置後面所有比插入元素大的有序元素全部右移一位，再將待插入的值放入對應位置。 這一點和上面介紹的優化點二做的事情一樣。 也就是說：折半插入排序在減少比較次數的同時， 也減少了元素移動次數。

折半插入排序代碼如下：

/** * @Author: HuWan Peng * @Date Created in 11:27 2017/12/2 */public class BinaryInsertSort { private static int binarySearch (int []a,int low,int high, int target) { int mid; while (low<=high) { mid = (low + high)/2; if(a[target]>a[mid]) { low = mid+1; } else { high = mid-1; } } return low; } public static void sort (int []a) { int N = a.length; for (int i=1;i<N;i++) { int temp = a[i]; int low = binarySearch(a,0,i-1,i); for(int j=i;j>low;j--){ a[j]=a[j-1]; } a[low]= temp; } }}

時間複雜度

折半插入排序在一定程度上優化了插排的性能， 但是因為它僅僅減少了關鍵字間的比較次數，而記錄的移動次數保持不變。因此，折半插入排序的時間複雜度仍然是O(n^2)

希爾排序（插入排序3.0）

出現的原因

總的來說，插入排序是一種基礎的排序方法，因為移動元素的次數較多， 對於大規模的複雜數組，它的排序性能表現並不理想。 而對於長度較短的、部分有序（或有序）的數組的處理，性能表現比較良好。

所以根據插排優於處理小型，部分有序數組的特性， 人們在插入排序的基礎上設計出一種能夠較好地處理中等規模的排序演算法： 希爾排序

實現的過程

希爾排序又叫做步長遞減插入排序或增量遞減插入排序

（下面的h就是步長）

1. 選擇一個遞增序列。並在遞增序列中，選擇小於數組長度的最大值，作為初始步長 h。

2. 開始的時候，將數組分為h個獨立的子數組(1中h)， 每個子數組中每個元素等距離分布，各個元素距離都是h。

3. 對2中分割出的子數組分別進行插入排序

4. 第一輪分組的插入排序完成後，根據遞增序列（逆向看）減少h的值並進行第二輪分組， 同樣對各個子數組分別插入排序。 不斷循環1、2、4, 直到h減少到1時候， 進行最後一輪插入排序，也就是針對整個數組的直接插入排序（這個時候分組只有1個，即整個數組本身）

5. 一開始的時候h的值是比較大的（例如可以佔到整個數組長度的一半），所以一開始的時候子數組的數量很多，而每個子數組長度很小。 隨著h的減小，子數組的數量越來越少，而單個子數組的長度越來越大。

【注意】 遞增序列的選擇是任意的 ， 但不同的遞增序列會影響排序的性能

下面的代碼中， 我們選擇的遞增序列是1,4 ,13,40,121,364,1093... 假設數組長度是N的話，一開始通過

while(h<N/3){ h=3*h+1; }

選擇初始步長， 並通過h = h/3，使h按照逆序的遞增序列減少，一直到1， 分別進行多輪分組插入排序。

代碼如下：

/** * @Author: HuWan Peng * @Date Created in 12:54 2017/12/2 */public class ShellSort { private static void exch(int []a,int i,int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } public static void sort (int [] a) { int N = a.length; int h = 1; while(h<N/3){ h=3*h+1; } // 在遞增序列1,4,13,40...中選擇小於數組長度的最大值，作為初始步長。 while (h>=1) { for (int i = h; i < N; i++) { for (int j = i; j >=h && a[j] < a[j - h]; j-=h) { exch(a, j, j - h); } } h = h/3; // 按照選定的遞增序列逆向減少 } }}

希爾排序圖示

為了方便展示,下面展示的是選定遞增序列為1...N/4,N/2的希爾排序的圖示（初始步長為h =N/2= 5, 並按照 h = h / 2的趨勢遞減）

（顏色相同表示的是同一個分組）

第一輪分組排序： h=5，所以將數組分為5組：7 1， 6 8， 3 1， 2 5， 9 0分別進行直接插入排序，得到

1 7， 6 8， 1 3， 2 5，9 0。 數組整體變為1 6 1 2 0 7 8 3 5 9

第二輪分組排序， h=2，所以將數組分為2組： 1 1 0 8 5， 6 2 7 3 9；經過分別的插入排序得到：

0 1 1 5 8， 2 3 6 7 9。數組整體變成 0 2 1 3 1 6 7 9。

第三輪分組排序， h=1， 所以就是對整個數組進行直接插入排序了

希爾排序分析

人們設計希爾排序的思路可以簡單描述為： 「對症下藥」， 因為插入排序擅長處理長度較短的， 部分有序（或有序）的數組， 那麼就按這兩點著手好了：

• 一開始的時候，每個子數組的長度短， 插入排序效率較高
• 每一輪分組排序後，數組有序性增強， 也提高了插入排序的效率。

關於第二點可以從希爾排序的柱狀軌跡圖看出（40-sorted表示此時 h =4）

每一輪的分組排序， 有序性都逐漸增強， 到最後一輪直接插入排序之前，數組已經接近完全有序了，這時候插排的效率是比較高的。

跑下題，這裡我再用一個比喻描述一下直接插入排序和希爾排序的關係：

奧特曼打小怪獸的時候，為什麼不直接上來就用大招消滅（對整個數組直接插入排序），而是到最後一步才放光波呢？ 理性一點可以這樣看： 一開始的時候怪獸還是滿血狀態（無序的大規模數組）， 這個時候放大招可能連怪獸都沒打死自己能量就全耗光了（總體排序性能太差）。 所以要採用「分步打法」（步長遞減插入排序），先用小招耗掉怪獸的血量（小型數組插排）， 等怪獸防禦力漸弱的時候（數組整體逐漸有序）才用祭出較強的大招（大型數組插排）和怪獸正面剛，到最後的時機到來的時候， 用光波滅掉血線已經降到斬殺階段的小怪獸，並不需要消耗太多的體力。（h=1時候對整個數組直接插排）

為何希爾排序後一定有序？

因為h到最後一定會減少到1，到最後就是對整個數組的直接插入排序

時間複雜度

關於希爾排序的時間複雜度，它和我們選擇的遞增序列有關， 在數學上研究起來比較複雜 ，且尚無定論

目前最重要的結論是：它的運行時間不到平方級別，也即時間複雜度小於O(n^2)， 例如我們上面選擇的1,4 ,13,40,121遞增序列的演算法， 在最壞情況下比較次數和N^(3/2)成正比。

推薦閱讀：