觀察一下”插入排序“：其實不難發現她有個缺點：

　　如果當數據是”5, 4, 3, 2, 1“的時候，此時我們將“無序塊”中的記錄插入到“有序塊”時，估計俺們要崩盤，每次插入都要移動位置，此時插入排序的效率可想而知。  

　　shell根據這個弱點進行了算法改進，融入了一種叫做“縮小增量排序法”的思想，其實也蠻簡單的，不過有點注意的就是：

增量不是亂取，而是有規律可循的。

希爾排序時效分析很難，關鍵碼的比較次數與記錄移動次數依賴于增量因子序列d的選取，特定情況下可以準確估算出關鍵碼的比較次數和記錄的移動次數。目前還沒有人給出選取最好的增量因子序列的方法。增量因子序列可以有各種取法，有取奇數的，也有取質數的，但需要注意：增量因子中除1 外沒有公因子，且最后一個增量因子必須為1。希爾排序方法是一個不穩定的排序方法。

首先要明確一下增量的取法(這里圖片是copy別人博客的，增量是奇數，我下面的編程用的是偶數)：

      第一次增量的取法為： d=count/2;

      第二次增量的取法為:  d=(count/2)/2;

      最后一直到: d=1; 

好，注意看圖了，第一趟的增量d1=5, 將10個待排記錄分為5個子序列，分別進行直接插入排序，結果為(13, 27, 49, 55, 04, 49, 38, 65, 97, 76)

第二趟的增量d2=3, 將10個待排記錄分為3個子序列，分別進行直接插入排序，結果為(13, 04, 49, 38, 27, 49, 55, 65, 97, 76)

第三趟的增量d3=1, 對整個序列進行直接插入排序，最后結果為(04, 13, 27, 38, 49, 49, 55, 65, 76, 97)

重點來了。當增量減小到1時，此時序列已基本有序，希爾排序的最后一趟就是接近最好情況的直接插入排序。可將前面各趟的"宏觀"調整看成是最后一趟的預處理，比只做一次直接插入排序效率更高。

本人是學python的，今天用python實現了希爾排序。

def ShellInsetSort(array, len_array, dk): # 直接插入排序 for i in range(dk, len_array): # 從下標為dk的數進行插入排序 position = i current_val = array[position] # 要插入的數 index = i j = int(index / dk) # index與dk的商 index = index - j * dk # while True: # 找到第一個的下標，在增量為dk中，第一個的下標index必然 0<=index<dk # index = index - dk # if 0<=index and index <dk: # break # position>index,要插入的數的下標必須得大于第一個下標 while position > index and current_val < array[position-dk]: array[position] = array[position-dk] # 往后移動 position = position-dk else: array[position] = current_valdef ShellSort(array, len_array): # 希爾排序 dk = int(len_array/2) # 增量 while(dk >= 1): ShellInsetSort(array, len_array, dk) print(">>:",array) dk = int(dk/2)if __name__ == "__main__": array = [49, 38, 65, 97, 76, 13, 27, 49, 55, 4] print(">:", array) ShellSort(array, len(array))