我們之前學過插入排序，它在數組大部分元素已經有序時效率很高，但如果數組完全無序或者逆序，每次只能移動一個元素，效率就比較低。希爾排序（Shell Sort）是插入排序的改進版，它通過分組的方式，讓數組先變得基本有序，再用插入排序處理，從而提高效率。
希爾排序的基本思想¶
希爾排序的核心是“分組”和“插入排序”。它不像插入排序那樣只比較相鄰元素，而是將數組分成若干組，每組內的元素間隔一定的距離（這個距離稱爲“增量”或“步長”），然後對每組內的元素進行插入排序。隨着增量逐漸減小，分組越來越細，直到增量爲1時，整個數組已經基本有序，此時插入排序就能快速完成。
希爾排序的步驟¶
- 選擇初始增量：通常初始增量取數組長度的一半（
n//2），然後每次將增量減半，直到增量爲0。 - 分組與插入排序：對於每個增量
gap，數組被分成gap個“組”，每個組內的元素下標相差gap。例如，數組長度爲10，gap=3時，組1是下標0、3、6、9，組2是下標1、4、7，組3是下標2、5、8。然後對每組內的元素進行插入排序。 - 重複調整增量：當增量減小到1時，整個數組已基本有序，此時插入排序能快速完成。
代碼實現（Python）¶
def shell_sort(arr):
n = len(arr)
gap = n // 2 # 初始增量爲數組長度的一半
while gap > 0:
# 遍歷每個組內的元素
for i in range(gap, n):
temp = arr[i] # 保存當前元素，避免被覆蓋
j = i - gap # 組內前一個元素的下標
# 將前面比temp大的元素後移
while j >= 0 and arr[j] > temp:
arr[j + gap] = arr[j] # 後移一位
j -= gap # 繼續向前比較
arr[j + gap] = temp # 將temp插入到正確位置
gap = gap // 2 # 增量減半，逐步縮小
return arr
代碼解釋：
- n = len(arr)：獲取數組長度，用於計算初始增量。
- gap = n // 2：初始增量爲數組長度的一半，這是最常用的簡單增量方式。
- while gap > 0：循環處理不同的增量，直到增量爲0。
- for i in range(gap, n)：遍歷每個組內的元素（從第gap個元素開始）。
- temp = arr[i]：保存當前元素，避免後續賦值覆蓋。
- j = i - gap：計算當前元素所在組的前一個元素下標。
- while j >= 0 and arr[j] > temp：若前一個元素比temp大，後移該元素並繼續向前比較；否則停止。
- arr[j + gap] = temp：找到合適位置後，將temp插入。
- gap = gap // 2：增量減半，逐步縮小分組，直到分組爲1（即普通插入排序）。
舉例說明（以數組[5, 3, 8, 4, 2]爲例）¶
-
初始數組：
[5, 3, 8, 4, 2]，n=5，初始增量gap=5//2=2。 -
處理
gap=2：
- 分組：組1（下標0、2、4：元素5、8、2），組2（下標1、3：元素3、4）。
- 組1插入排序：i=2（元素8）：j=0（i-gap=0），arr[0]=5 <=8，無需移動。數組不變：[5,3,8,4,2]。i=4（元素2）：j=4-2=2（arr[2]=8>2），後移8到arr[4]，數組變爲[5,3,2,4,8]；j=0（arr[0]=5>2），後移5到arr[2]，數組變爲[5,3,5,4,8]；j=-2（找到位置），插入2到arr[0]，組1排序後：[2,3,5,4,8]。- 組2插入排序：
i=3（元素4）：j=3-2=1（arr[1]=3 <=4），無需移動。數組不變：[2,3,5,4,8]。
-
處理
gap=1（此時增量減半爲1，即普通插入排序）：
-i=1（元素3）：j=0（arr[0]=2 <=3），不動。
-i=2（元素5）：j=1（arr[1]=3 <=5），不動。
-i=3（元素4）：j=2（arr[2]=5>4），後移5到arr[3]，數組變爲[2,3,5,5,8]；j=1（arr[1]=3 <=4），插入4到arr[2]，數組變爲[2,3,4,5,8]。
-i=4（元素8）：j=3（arr[3]=5 <=8），不動。 -
最終結果：
[2, 3, 4, 5, 8]。
總結¶
- 時間複雜度：平均約爲O(n log n)，最壞情況爲O(n²)，比插入排序更高效。
- 空間複雜度：O(1)，原地排序，僅需臨時變量。
- 適用場景：適用於中等規模數組，尤其當元素分佈不均勻時，分組排序可減少移動次數。
通過分組和逐步縮小增量，希爾排序讓數組先“粗排”再“精排”，有效提升了插入排序的效率，是一種實用的排序算法。