一、希爾排序的介紹 希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法。 希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的記錄越來越多，當增量減至1時，整個文件恰被分 ...
一、希爾排序的介紹
希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法。 希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的記錄越來越多，當增量減至1時，整個文件恰被分成一組，演算法便終止。
二、希爾排序的原理
在前面文章中介紹的直接插入排序，它對於已經基本有序的數據進行排序，效率會很高，而如果對於最初的數據是倒序排列的，則每次比較都需要移動數據，導致演算法效率降低。
希爾排序的基本思想就是：將需要排序的序列邏輯上劃分為若幹個較小的序列（但並非真的分割成若幹分區），對這些邏輯上序列進行直接插入排序，通過這樣的操作可使需要排序的數列基本有序，最後再使用一次直接插入排序。
在希爾排序中首先要解決的是怎樣劃分序列，對於子序列的構成不是簡單地分段，而是採取將相隔某個增量的數據組成一個序列。一般選擇增量的規則是：取上一個增量的一半作為此次子序列劃分的增量，一般初始值元素的總數量的一半。
三、希爾排序的圖解
四、希爾排序的python代碼實現
# 創建一個希爾排序的函數 def shell_sort(alist): # 需要排序數組的個數 N = len(alist) # 最初選取的步長 gap = N//2 # 根據每次不同的步長，對分組內的數據進行排序 # 如果步長沒有減為1就繼續執行 while gap>0: # 對每個分組進行插入排序， # 因為插入排序從第二個元素開始，而這裡第二個元素的下標就是gap # 所以i的起始點是gap for i in range(gap,N): # 控制每個分組內相鄰的兩個元素,邏輯上相鄰的兩個元素間距為gap， # j的前一個元素比它少一個gap距離，所以for迴圈中j的步長為 -gap for j in range(i,0,-gap): # 判斷和邏輯上的分組相鄰的兩個數據大小 if alist[j]<alist[j-gap] and j-gap>=0: # 交換 temp = alist[j] alist[j] = alist[j-gap] alist[j-gap] = temp # 改變步長 gap = gap//2 numlist = [5,7,8,3,1,2,4,6,9] print("排序前：%s"%numlist) shell_sort(numlist) print("排序後：%s"%numlist)
運行結果為：
排序前：[5, 7, 8, 3, 1, 2, 4, 6, 9]
排序後：[1, 2, 3, 4, 5, 6, 7, 8, 9]
五、希爾排序的C語言實現
#include <stdio.h> // 創建一個希爾排序的函數 void shell_sort(int arr[],int arrLength,int gap) { // 根據每次不同的步長，對分組內的數據進行排序 // 如果步長沒有減為1就繼續執行 while (gap>0) { // 對每個分組進行插入排序， // 因為插入排序從第二個元素開始，而這裡第二個元素的下標就是gap， // 所以i的起始點是gap for (int i = gap; i<arrLength; i++) { // 控制每個分組內相鄰的兩個元素,邏輯上相鄰的兩個元素間距為gap， // j的前一個元素比它少一個gap距離，所以for迴圈中j每次減少一個gap // 因為j-gap是上一個元素的下標，也必須保證大於等於0 for (int j = i; j>0&&j-gap>=0; j=j-gap) { // 判斷和邏輯上的分組相鄰的兩個數據大小 if (arr[j]<arr[j-gap]) { // 交換 int temp = arr[j]; arr[j] = arr[j-gap]; arr[j-gap] = temp; } } } gap = gap/2; } } int main(int argc, const char * argv[]) { // 定義數組 int array[] = {5,7,8,3,1,2,4,6,9}; // 希爾排序的聲明 void shell_sort(int arr[],int arrLength,int gap); // 計算數組長度 int len = sizeof(array)/sizeof(int); // 制定gap為二分之一的長度 int g = len/2; // 使用希爾排序 shell_sort(array, len, g); // 驗證 for (int i = 0; i<len; i++) { printf("%d ",array[i]); } return 0; }
運行結果為：
1 2 3 4 5 6 7 8 9
六、希爾排序的時間複雜度
- 最優時間複雜度：根據步長序列的不同而不同
- 最壞時間複雜度：O(n2)
七、希爾排序的穩定性
由於多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最後其穩定性就會被打亂，所以shell排序是不穩定的。
