前言

上期我们介绍了直接插入排序，对他的基本思想和复杂度进行了分析。在这个过程中，我们发现虽然直接插入排序是一种稳定的算法，但是它的时间复杂度太慢了。这时，就推出我们金天要讲的直接插入排序的优化版——希尔排序

什么是希尔排序

中百度百科上我们可以查到:希尔排序 (Shell's Sort)是的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。希尔排序是把记录按的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

发展历程

希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由希尔在 1959 年所发表的论文“A high-speed sorting procedure” 中所描述。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

1.插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
2.但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

1961年，IBM 公司的女程序员 Marlene Metzner Norton（玛琳·梅茨纳·诺顿）首次使用 FORTRAN 语言编程实现了希尔排序算法。在其程序中使用了一种简易有效的方法设置希尔排序所需的增量序列：第一个增量取待排序记录个数的一半，然后逐次减半，最后一个增量为 1。该算法后来被称为 Shell-Metzner 算法，Metzner 本人在2003年的一封电子邮件中说道：“我没有为这种算法做任何事，我的名字不应该出现在算法的名字中。”

希尔排序的实现

基本思想

1 先取一个长度len/2的数d1作为第一个增量，再把需要排序数组的元素全部记录分组。

2 所有距离为d1的倍数的元素放在同一个组中。

3 然后在各组内进行插入排序。

4 然后，取第二个增量d2=d1/2 ，d3=d2/2……对重复以上操作，每次增量都/2，直到最后变成1。

具体代码

#include <stdio.h>
void ShellSort(int* arr, int len)
{
  //gap是步长
  int gap = len / 2;
  //每一次都折半，直到最后为1，就成一个数组了
  for (; gap > 0; gap /= 2)
  {
    int i = 0;
    //这里共有gap个被分解的数组 分别对它们直接插入排序
    for (i = 0; i < gap; i++)
    {
      int j = 0;
      //这里是一个数组中的元素
      for (j =i + gap; j < len; j += gap)
      {
        //如果需比较的元素小于前一个元素就进入
        if (arr[j] < arr[j - gap])
        {
          //用哨兵tmp将需比较元素存储起来
          int tmp = arr[j];
          //k就是带比较的前一个元素的下标
          int k = j - gap;
          //k就是限制范围，不能超出数组
          //arr[k]>tmp 就进行交换
          while (k >= 0 && arr[k]>tmp)
          {
            arr[k + gap] = arr[k];
            //减去gap就到了前一个元素
            //为下一次需比较的元素比较做准备
            k -= gap;
          } 
          //比较完后将tmp放入它合适的位子
          //因为上面-gap，所以需要+回来
          arr[k + gap] = tmp;
        }
      }
    }
  }
}
int main()
{
  //需处理的数组
  int arr[] = {10, 9,8,7,6,5,4,3,2,1 };
  //希尔排序
  ShellSort(arr, sizeof(arr) / sizeof(arr[0]));
  //打印
  int i = 0;
  for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
  {
    printf("%d ", arr[i]);
  }
  return 0;
}

希尔排序的原理

该方法实质上是一种分组插入方法

比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行分组，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。一般的初次取序列的一半为增量，以后每次减半，直到增量为1。

我们以代码中的数组为例：

我们发现数组有10个元素.我们第一次的增量为元素的一半gap=len/2=5.然后我们就将5的倍数的元素分为一组，这里是10 5，9 4，8 3，7 2，6 1分别为一组，然后进行插入排序。就是5 4 3 2 1 10 9 8 7 6 这里要注意我们排序完后插入的是它们的相对位置。我们再进行第二次排序：gap=5/2=2，这里就是5 3 2 1 9，4 2 10 8 6分别为一组，仍然后进行插入排序。就是1 2 3 4 5 6 7 8 9 10。第三次排序：这时gap=2/2=1了，就只有一个数组，直接插入排序就可以了，最后的结果就是1 2 3 4 5 6 7 8 9 10这里数组列的有点特殊。这样子我们一个希尔排序就已经全部完成了。

为什么希尔排序优于插入排序

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。

希尔排序的时间性能优于直接插入排序的原因：

①当数组初态基本有序时直接插入排序所需的比较和移动次数均较少。

②当n值较小时，n和的差别也较小，即直接插入排序的最好复杂度O(n)和最坏时间复杂度0()差别不大。

③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。

因此，希尔排序在效率上较直接插入排序有较大的改进。

希尔排序的优缺点

它需要大量的辅助空间，和归并排序一样容易实现。希尔排序是基于插入排序的一种算法，在此算法基础之上增加了一个新的特性，提高了效率。希尔排序的时间的时间复杂度为O(n3/2），希尔排序时间复杂度的下界是n*log2n。希尔排序没有快速排序快 O(n(logn))，因此中等大小规模表现良好，但是对于规模非常大的数据排序不是最优选择。但是比O(n^2)复杂度的算法也就是直接插入排序快得多。并且希尔排序非常容易实现，算法代码短而简单。此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。所以建议几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法. 本质上讲，希尔排序算法是直接插入排序算法的一种改进，减少了其复制的次数，速度要快很多。原因是，当n值很大时数据项每一趟排序需要移动的个数很少，但数据项的距离很长。当n值减小时每一趟需要移动的数据增多，此时已经接近于它们排序后的最终位置。正是这两种情况的结合才使希尔排序效率比插入排序高很多。

希尔排序的实现让你改进直插排序速度慢的缺陷

前言