前言

希爾排序是什么？

希爾排序(Shell Sort)是插入排序的一種。是針對直接插入排序算法的改進版本。該方法又稱縮小增量排序或者遞減增量排序算法，跟插入排序不一樣的是希爾排序是非穩定排序算法。因D.L.Shell于1959年提出而得名。

希爾排序算法實質上是一種分組插入方法。他的基本思想如下:

設待排序元素序列有n個元素,選擇一個增量序列 d1，d2，……，dt，其中 di > dj, dt = 1；先取一個小于n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為d1的倍數的記錄放在同一個組中。先在各組內進行直接插入排序(之前寫過一篇關于插入排序的文章,這里就不再贅述,需要的童鞋可點擊連接了解《??【算法實踐】手把手帶你快速實現插入排序??》)；然后，取第二個增量d2

(相關資料圖)

注：由于開始時，dt的取值較大，每個子序列中的元素較少，排序速度較快，到排序后期dt取值逐漸變小，子序列中元素個數逐漸增多，但由于前面工作的基礎，大多數元素已經基本有序，所以排序速度仍然很快。

希爾排序是基于插入排序的以下兩點性質而提出改進方法的：

插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位

下圖是插入排序和希爾排序的對比:

希爾排序的平均時間復雜度:O(nlogn) 最好情況和最壞情況都是O(n?logn2),空間復雜度是O(1),是一種不穩定排序.

圖解希爾排序

增量序列 d1，d2，……，dt，其中 di > dj, dt = 1

按增量序列個數 k，對序列進行 k 趟排序；

每趟排序，根據對應的增量dt，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

如現有以下n(6)個數:排序前: [22, 23, 48, 23, 18, 7]

希爾排序中增量的取法:

增量dt的取法有各種方案。最初shell提出取dt=n/2向下取整，dt=dt/2向下取整，直到dt=1。但由于直到最后一步，在奇數位置的元素才會與偶數位置的元素進行比較，這樣使用這個序列的效率會很低。后來Knuth提出取dt=n/3向下取整+1.還有人提出都取奇數為好，也有人提出dt互質為好。應用不同的序列會使希爾排序算法的性能有很大的差異

增量dt的取值方法是：(n/3的值向下取整 )+ 1

第一趟排序dt的取值為(6/3的值向下取整 )+ 1=3,即對比的數據間隔為3,分成3組第二趟排序dt的取值為(3/3的值向下取整 )+ 1=2,即對比的數據間隔為2,一共分成2組第三趟排序dt的取值為(2/3的值向下取整 )+ 1=1,即對比的數據間隔為1,兩兩比較只剩下一個分組

直到dt=1時，就是對整個數列做最后一次調整，因為前面的序列調整已經使得整個序列部分有序，所以最后一次調整也變得非常快

從上面的圖示中可以看到粉紅色方塊的23本來在紫色方塊的23前面,排序完成后,粉紅色方塊的23排序到紫色方塊的23后面,可看出希爾排序是個不穩定的排序算法.

代碼實現

導入math庫,math庫是Python內置的標準庫,里面定義了與數學相關的函數

import math

定義排序函數shellSort():

def shellSort(arr):    gap=1    while(gap < len(arr)/3):        gap = gap*3+1    while gap > 0:        for i in range(gap,len(arr)):            temp = arr[i]            j = i-gap            while j >=0 and arr[j] > temp:                arr[j+gap]=arr[j]                j-=gap            arr[j+gap] = temp        gap = math.floor(gap/3)    return arr

驗證算法:

arrList = [22,23,48,23,18,7]print("排序前:",arrList)sortedArr = shellSort(arrList)print("排序后:",sortedArr)

執行結果如下: