📋 前言
希尔排序，不知道大家有没有感觉听起来都很吊吊的样子。事实也确实如此，希尔排序的性能在八大排序中某些特定情况是最强的，也是我们必学的高效算法之一。
一、什么是希尔排序
希尔排序，也称为缩小增量排序，是插入排序的一种高效改进版本也可以把它
- 看做为插入排序的优化版
希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序
二、希尔排序的思想与实现
既然希尔排序是分组来实现的，那么这样做的好处呢？其实是因为每次分组跳着来进行选择排序，可以更快的吧大数调整到后面：
而插入排序却需要需要排 N*N 次才能找到最大值（最坏情况）
如上图当排的分组的区间为2的时候每次只需要排一次就可以达到全部有序了。
2.1 希尔排序的版本一
当我们看到分组的时候肯定大部分想的都是 定义一个 gap组然后再进行每次排序一直重复到 1 ；
- 这里需要注意的是数据被分成了 gap组那么每次进行交换
- 都需要间隔 gap 组
而被分成了 gap 组那么每次都需要排序gap次所以需要一个外循环
🍸 代码演示：
// 希尔排序 void ShellSort(int* a, int n) { //方法一普通想法 int gap = 3; for (int j = gap; j > 0; j--) { for (int i = j; i < n-j; i++) { int end = i; int tmp = a[end+j]; while (end >= 0) { if (a[end] > tmp) { a[end + j] = a[end]; } else { break; } end = end-j; } a[end + j] = tmp; } } }
以上就是普通实现的希尔排序的代码了，而第二组排序的时候就是从第二个数据开始了：
- 所以 i = j, 而每次需要跨越 gap 个数据
2.2 希尔排序的优化版本
但是上述代码有很大的局限性，希尔排序在排序每次 需要的 gap 分组都不一样：
- 一般我们是采用 gap = n/2
- 优化一下也可以写成 gap = n/3 +1
gap = n/3 +1 为什么要+1 呢因为当时候 2/3 的时候编译器回默认为 0 ，但我们这次还需要再排序一次数据所以需要+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; } } }
二、希尔排序的性能
希尔排序的特性总结：
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
- 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定：
《数据结构(C语言版)》— 严蔚敏
《数据结构-用面相对象方法与C++描述》— 殷人昆
因为咋们的gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照：O ( n 1.25 ) O(n^{1.25})O(n1.25) 到 O ( 1.6 ∗ n 1.25 ) O(1.6*n^{1.25})O(1.6∗n1.25)来算。
- 稳定性：不稳定
