简介：
希尔排序法⼜称缩⼩增量法。是一种基于插入排序的高效排序算法，由美国计算机科学家Donald Shell于1959年提出。
基本思想：
先选定⼀个整数（通常是gap=n/3+1），把 待排序⽂件所有记录分成各组，所有的距离相等的记录分在同⼀组内，并对每⼀组内的记录进⾏排 序，然后gap=gap/3+1得到下⼀个整数，再将数组分成各组，进⾏插⼊排序，当gap=1时，就相当于 直接插⼊排序。
比较：（直接插入排序）
它是在直接插⼊排序算法的基础上进⾏改进⽽来的，综合来说它的效率肯定是要⾼于直接插⼊排序算 法的。
思路：（如图）
算法实现：
思路一：
//代码一：void ShellSort(int* a, int n) {int gap = n;while (gap > 1) {gap = gap / 3 + 1;for (int i = 0; i < n - gap; ++i) {int end = i;int tmp = a[end + gap];while (end >= 0) {if (a[end] > tmp) {a[end + gap] = a[end];end -= gap;}else {break;}}a[end + gap] = tmp;}}
}思路二：
class Solution {
public:int ShellSort(vector<int>& num) {int n = num.size();int gap = n;while (gap > 1) {gap = gap / 3 + 1;for (int i = 0; i < n - gap; ++i) {int end = i, tmp = num[end + gap];while (end >= 0) {if (num[end] > tmp) {num[end + gap] = num[end];end -= gap;}else {break;}}num[end + gap] = tmp;}}}
};
总结：
特点：
希尔排序是对直接插⼊排序的优化。
当 gap > 1 时都是预排序，⽬的是让数组更接近于有序。
复杂度：
希尔排序时间复杂度不好计算，因为 gap 的取值很多，导致很难去计算，因此很多书中给出的希尔排序的时间复杂度都不固定。
这部分要证明的话太难了，大家如果感兴趣的话可以去了解一下严蔚敏在《数据结构(C语⾔版)》一书中给出的时间复杂度详解。