*****
## 希爾排序
希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因DL．Shell于1959年提出而得名。 希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。
### 希爾排序過程
希爾排序的基本思想是：將數組列在一個表中并對列分別進行插入排序，重復這過程，不過每次用更長的列（步長更長了，列數更少了）來進行。最后整個表就只有一列了。將數組轉換至表是為了更好地理解這算法，算法本身還是使用數組進行排序。
例如，假設有這樣一組數[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我們以步長為5開始進行排序，我們可以通過將這列表放在有5列的表中來更好地描述算法，這樣他們就應該看起來是這樣(豎著的元素是步長組成)：
```
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
```
然后我們對每列進行排序：
```
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
```
將上述四行數字，依序接在一起時我們得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。這時10已經移至正確位置了，然后再以3為步長進行排序：
```
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
```
排序之后變為：
```
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
```
### 希爾排序實現
```
def shell_sort(li):
n = len(li)
# 初始步長
gap = n // 2
while gap > 0:
# 按步長進行插入排序 4-8
for i in range(gap, n):
# 插入排序
while i >= gap and li[i - gap] > li[i]:
li[i - gap], li[i] = li[i], li[i - gap]
i -= gap
# 得到新的步長
gap = gap // 2
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
shell_sort(li)
print(li)
```
### 時間復雜度
- 最優時間復雜度：根據步長序列的不同而不同
- 最壞時間復雜度：O(n2)
- 穩定想：不穩定
