1 希爾排序

希爾排序（Shell Sort）是D.L.Shell于1959年提出來的一種排序算法，在這之前排序算法的時間復雜度基本都是O(n2)，希爾排序算法是突破這個時間復雜度的第一批算法之一。

1.1 基本概念與原理

希爾排序通過將原始列表分割成若干子序列進行插入排序，隨著增量逐漸減小，最終對整個列表進行一次插入排序。
核心思想
?1.增量序列?：選擇一個增量序列(gap sequence)，將數組分成若干子序列
?2.子序列排序?：對每個子序列進行插入排序
?3.逐步縮小增量?：重復上述過程，直到增量為1
?4.最終排序?：當增量為1時，對整個數組進行最后一次插入排序
希爾排序之所以高效，是因為它利用了插入排序在"部分有序"數組上表現良好的特性。通過前期的大增量排序，使得數組逐漸趨于有序，減少了后期小增量排序時的數據移動次數。

1.2 算法執行過程

1.增量序列選擇
希爾排序的性能很大程度上取決于增量序列的選擇。常見的增量序列有：
Shell原始序列：n/2, n/4, …, 1
Hibbard序列：1, 3, 7, …, 2^k - 1
Sedgewick序列：1, 5, 19, 41, 109,…
2. 具體執行步驟
以數組[8, 3, 9, 1, 5, 7, 2, 6]為例，使用Shell原始序列(n/2, n/4,…)：
?初始數組?：[8, 3, 9, 1, 5, 7, 2, 6] (n=8)
?第一輪(gap=4，分成4組序列)?：
子序列1：[8,5] → [5,8]
子序列2：[3,7] → [3,7]
子序列3：[9,2] → [2,9]
子序列4：[1,6] → [1,6]
?結果?：[5, 3, 2, 1, 8, 7, 9, 6]
?第二輪(gap=2，分成2組序列)?：
子序列1：[5,2,8,9] → [2,5,8,9]
子序列2：[3,1,7,6] → [1,3,6,7]
?結果?：[2, 1, 5, 3, 8, 6, 9, 7]
?第三輪(gap=1，分成1組序列)?：
對整個數組進行插入排序
?最終結果?：[1, 2, 3, 5, 6, 7, 8, 9]

1.3 算法復雜度分析

時間復雜度
希爾排序的時間復雜度分析較為復雜，因為它依賴于增量序列的選擇：
?最壞情況?：O(n2) - 當增量序列不佳時
?平均情況?：
Shell原始序列：O(n^(3/2))
Hibbard序列：O(n^(3/2))
Sedgewick序列：O(n^(4/3))
?最好情況?：O(nlogn) - 當數組已經部分有序時
空間復雜度
希爾排序是原地排序算法，空間復雜度為O(1)。
穩定性
希爾排序是不穩定的排序算法，因為相同的元素可能在各自的插入排序中移動。

1.4 C語言實現希爾排序

#include <stdio.h>#define SORT_DATA_TYPE int/*** @brief 打印數據** @param arr 數組* @param n 數組元素個數*/
void print_array(int arr[], int n)
{int i;for (i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}/*** @brief 希爾排序** @param arr 待排序的數組* @param n 數組元素個數*/
void shell_sort(int arr[], int n)
{SORT_DATA_TYPE temp;int gap;int i, j;/* 初始增量gap為數組長度的一半，逐步縮小 */for (gap = n / 2; gap > 0; gap /= 2){/* 從第gap個元素開始，逐個對其所在子序列進行插入排序 */for (i = gap; i < n; i++){temp = arr[i];/* 對子序列進行插入排序 */for (j = i; j >= gap; j -= gap){if (arr[j - gap] > temp){arr[j] = arr[j - gap];}else{break;}}arr[j] = temp;print_array(arr, n); /* 查看每次排序結構，調試使用 */}printf("result :"); /* 查看每次排序結構，調試使用 */print_array(arr, n);}
}int main()
{SORT_DATA_TYPE arr[] = {4, 3, 2, 1};int n = sizeof(arr) / sizeof(arr[0]);printf("old arr : ");print_array(arr, n);shell_sort(arr, n);printf("new arr : ");print_array(arr, n);return 0;
}

注：
不同類型的數組直接將SORT_DATA_TYPE全部替換為需要的類型，然后刪除多余的宏定義即可支持任意類型數組的希爾排序。

1.5 簡單測試

通過使用數組[4,3,2,1]演示希爾排序的執行過程：

可以使用如下圖片演示這一過程：