数据结构----希尔排序

一、基本思想

希尔排序又称缩小增量排序，是直接插入排序的改进版。
核心思路：
先把整个数组按下标分成若干组，每组间隔为 增量 d；
对每一组内部分别做直接插入排序；
逐步缩小增量 d，重复分组、组内插入排序；
最后一趟增量 d = 1，退化成普通直接插入排序，此时数组已基本有序，排序极快。
一句话总结：先宏观粗略有序，再微观精细插入。

二、为什么比直接插入快

直接插入在逆序、乱序时，元素移动次数非常多；
希尔排序一开始远距离交换，把小元素快速挪到前面、大元素挪到后面；
后期数组接近有序，直接插入效率极高。

三、增量选取规则

四、算法执行步骤
设定初始增量 d=n/2；
按间隔 d 分组：下标 0,d,2d... 一组，1,d+1,2d+1... 一组；
每组内部进行直接插入排序；
增量减半 d=d/2，重复分组排序；当 d=1完成最后一趟直接插入，整体有序。

五、完整 C 语言代码

#include <stdio.h> // 希尔排序 void ShellSort(int a[], int n) { int i, j, temp; // 增量d 初始n/2，每次折半缩小 for(int d = n / 2; d > 0; d = d / 2) { // 组内直接插入排序 for(i = d; i < n; i++) { temp = a[i]; // 同组向前比较，间隔为d for(j = i - d; j >= 0 && a[j] > temp; j -= d) { a[j + d] = a[j]; } a[j + d] = temp; } } } // 打印数组 void Print(int a[], int n) { for(int i = 0; i < n; i++) printf("%d ", a[i]); printf("\n"); } int main() { int arr[] = {49, 38, 65, 97, 76, 13, 27, 49}; int len = sizeof(arr) / sizeof(arr[0]); ShellSort(arr, len); Print(arr, len); return 0; }

六、代码逐行解析

for(int d = n/2; d > 0; d = d/2)控制增量变化：初始折半，逐次折半，直到 d=1。
for(i = d; i < n; i++)从第 d 个元素开始，逐个处理每组元素。
temp = a[i]暂存当前要插入的元素。
for(j = i-d; j >= 0 && a[j] > temp; j -= d)
j = i-d：同组前一个元素
j -= d：继续向前找同组前驱
比 temp 大的元素，向后挪 d 个位置
a[j + d] = temp
找到合适位置，插入元素。

七、性能分析

时间复杂度
最坏：O(n 2)
平均：O(n 1.3)左右
优于直接插入、冒泡、简单选择。
空间复杂度仅常数变量：O(1)就地排序
稳定性不稳定排序远距离分组交换，会打乱相等元素相对位置。

八、四大特点必背

属于插入类排序；
先分组粗排，后精细插入；
不稳定、就地排序；
越乱序的数据，提升效果越明显；接近有序时优势变小。

九、插入类排序总结

直接插入：简单、稳定、O(n 2)
折半插入：减少比较次数、仍 O(n 2 )、稳定
希尔排序：分组增量优化、O(n 1.3)、不稳定