图解希尔排序——希尔排序算法(shell sort)

希尔排序又叫缩小增量排序，它是对直接插入排序算法的一种改进。希尔排序算法的基本思想是先将整个待排序的序列划分为若干个子序列，然后分别对子序列排序，逐步缩小划分子序列的间隔，直到划分间隔为1时排序完成。

算法图解

首先给定一个序列[7, 26, 9, 11, 23, 14]

第一趟排序： 按间隔为3划分为三个子序列，对三个子序列分别进行排序，满足从小到大则不动，否则交换两个元素位置。

第二趟排序： 按间隔为2划分子序列，共划分出两个子序列，对两个子序列分别排序

第三趟排序： 按间隔为1划分进行排序

在希尔排序中有一个关键问题就是如何选取划分间隔，一种常用的间隔划分方法是：首先间隔取原始序列长度的一半，在后续排序过程中，后一趟排序的间隔为前一趟排序的间隔的一半。实际上，在业界有一个统一的公式来求划分间隔：gap = gap / 3 + 1。

算法实现（C语言）

void shell_sort(int array[], int len) 
{
  int i = 0, j = 0, k = 0, temp = 0, gap = 0;
  gap = len;
  do
  {
    gap = gap / 3 + 1;
    for(i = gap; i < len; i += gap)
    {
      k = i;
      temp = array[k];
      for(j = i - gap; (j >= 0) && (array[j] > temp); j -= gap)
      {
        array[j + gap] = array[j];
        k = j;
      }
      array[k] = temp;
    }
  }
  while(gap > 1);
}

算法分析

稳定性分析

根据上面的图示可以看出，希尔排序是不稳定的，因为希尔排序是划分子序列对子序列分别排序，如果不同子序列中有相等的数，但它们不在同一子序列中，可能会因为子序列内部排序而改变原有的顺序。比如下图所示，原始序列中有两个11，经过一趟希尔排序后，原本在后面的紫色11跑到了前面位置，所以希尔排序是不稳定的。

复杂度分析

希尔排序并不是简单的随意分组，然后各自排序，希尔排序的精髓在于按照某个增量来划分子序列（最后一个增量必须是1），实现跳跃式移动来提高排序效率，而也正是这种跳跃性带来了不稳定性。

希尔排序的时间复杂度是O(nlogn)，希尔排序是最早突破排序算法复杂度O(n×n)的算法之一，从此排序算法时间复杂度不可突破O(n×n)的说法也不攻自破，并且分组划分的思想为后来很多更高效的排序算法提供了思路。