1 希尔排序

希尔排序（Shell Sort）是D.L.Shell于1959年提出来的一种排序算法，在这之前排序算法的时间复杂度基本都是O(n²)，希尔排序算法是突破这个时间复杂度的第一批算法之一。

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(n²) - 当增量序列不佳时
‌平均情况‌：
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;
}