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;
}
注：
不同类型的数组直接将SORT_DATA_TYPE全部替换为需要的类型，然后删除多余的宏定义即可支持任意类型数组的希尔排序。
1.5 简单测试
通过使用数组[4,3,2,1]演示希尔排序的执行过程：
可以使用如下图片演示这一过程：
