【七类排序】之第五种：希尔排序

大家久等了， 希尔排序（Shell Sort）由Shell在50年代末提出， 其思想是分组插入排序。希尔排序也是我最喜欢的排序之一， 一来感觉很多人不了解希尔排序， 所以可以对很多人卖弄， 二来，可以加深对 分组策略， 插入排序的理解。

注：若无特殊说明， 排序目的为递增。
何为分组插入排序？ 基本算法是：

1：先将数组分成gap组子数组（由变量gap决定，组内相邻元素间隔值为gap）
2：然后每一组子列分别进行插入排序， gap=gap/2
3: 重复步骤1,2， 直到gap=0，数组排序结束。

用实例来说明吧， 设存在长度为10的数组。

第一次分组排序：

gap=10/2=5,于是将数组分成5组。

59	98	33	78	86	23	19	64	23	100
1a	2a	3a	4a	5a	1b	2b	3b	4b	5b

说明： 阿拉伯数字相同的为一组， 一共gap组， 即5组{59， 23} {98， 19} {33， 64} {78， 23} {86， 100}
我们分组目的是， 对分成的gap个子数组的组内进行插入排序。（插入排序请看教程2：http://www.1point3acres.com/bbs/thread-44082-1-1.html）

希尔排序算法为什么分组？ 精髓就在这里： 因为插入排序对于基本的case，有序或者大部分有序的case效率是很高的， 其次实现也非常简单。

回到正题， 我们对5组{59， 23} {98， 19} {33， 64} {78， 23} {86， 100}插入排序后， 得到{23， 59} {19， 98} {33， 64} {23， 78} {86， 100}

第二次分组排序：

第一次分组排序后，数组变成如下， gap=5/2=2。

23	19	33	23	86	59	98	64	78	100
1a	2a	1b	2b	1c	2c	1d	2d	1e	2f

gap=2于是数组分成2组{23,33,86,98,78} {19,23,59，64,100}， 不知道各位发现了没有， 每组的元素已经非常有序了， 这正是插入排序想看到的。
排序后数组为：

23

19

33

23

78

59

86

64

98

100

第三次分组排序：

gap=2/2=1, 因此只有一组了， 就是原数组本身：

23	19	33	23	78	59	86	64	98	100
1a	1b	1c	1d	1e	1f	1g	1h	1i	1j

此时再做一次插入排序即可，下一次gap=1/2=0， 排序完毕如下：
19 23 23 33 59 64 78 86 98 100

按照算法步骤， 我们严格实现代码：

void ShellSort(int[] a, int n)
{
    int gap=n/2;
    while (gap>0)
    {
         //分组处理
        for (int i=0; i<gap; i++)
            for (int j=i+gap; j<n; j+=gap)
                if (a[j]<a[j-gap])
               {
                   int t=a[j];
                   int k=j-gap;
                   while (k>=0 && a[k]>t)
                   {
                       a[k+gap]=a[k];
                        k-=gap;
                    }
                    a[k+gap]=t;

                }
         gap=gap/2;
      }
}


改进1： 我们用不着每次让i从0循环到gap-1这个遍历， 直接从gap, gap+1开始就行了。 于是 上面的第二层循环可以免了，代码如下。
void ShellSort(int[] a, int n)
{
    int gap=n/2;
    while (gap>0)
    {
            for (int j=gap; j<n; j++)
                if (a[j]<a[j-gap])
               {
                   int t=a[j];
                   int k=j-gap;
                   while (k>=0 && a[k]>t)
                   {
                       a[k+gap]=a[k];
                        k-=gap;
                    }
                    a[k+gap]=t;
                }
         gap=gap/2;
      }
}


改进2：我们在改进1的基础上， 使用插入排序的最简写法, 把最外层while循环改写成for循环。

void ShellSort(int[] a, int n)
{
    for (int gap=n/2; gap>0; gap/=2)
         for (int j=gap; j<n && a[j]<a[j-gap]; j++)
             for (int k=j; k-gap>=0 && a[k]<a[k-gap]; k-=gap)  
                 swap(a[k], a[k-gap]);
}


很简洁， 有木有？！

总结： gap其实怎么设定都不影响算法的正确性， 但我们一般采用gap=n/2，然后每次减半。 其实gap的选择猫腻可不少，这里就不介绍了，  请读者自行研究。送上链接
http://zh.wikipedia.org/wiki/%E5 ... F.E5.BA.8F.E5.88.97

这么好的帖子怎么没人留言？长期潜水的贫农特意来顶一下~~~

记得好久以前也学过希尔排序，现在再看却“如初见”了。。。受教了~

期待LZ新作~

楼主辛苦了，赞一下
我看了下有几个地方觉得有些问题，似乎是笔误？
1. 最内层的插入排序：

1. int t=a[j];
   
2.                  int k=j-gap;
   
3.                    while (k>=0 && a[k]>a[k+gap])
   
4.                    {
   
5.                        a[k+gap]=a[k];
   
6.                         k-=gap;
   
7.                     }
   
8.                     a[k+gap]=t;
   

复制代码

while 中的比较应该是 a[k]>t ，每次和t 比较来判断是否要对t做插入，而不是每次比较相邻的两个，你自己提供链接到维基百科中，也提供了C代码示例，其最内层插入排序：

1. j = i - gap;
   
2.              temp = a[i];            
   
3.              while (( j >= 0 ) && ( a[j] > temp ))
   
4.              {
   
5.                  a[j + gap] = a[j];
   
6.                  j = j - gap;
   
7.              }
   
8.              a[j + gap] = temp;

复制代码

这里temp 相当于你的t
j 相当于你的k

不知道是我理解有误还是这里确实有些问题？

2.  最后改进2的部分，你写的变量k明显没有用到，我贴一下C_PROGRAMMING_LANGUAGE中的shell sort code，和你改进后的应该是一个意思：

1. void shellsort(int v[], int n)
   
2. {
   
3. int gap, i, j, temp;
   
4. for (gap = n/2; gap > 0; gap /= 2)
   
5.    for (i = gap; i < n; i++)
   
6.       for (j=i-gap; j>=0 && v[j]>v[j+gap]; j-=gap) {
   
7.          temp = v[j];
   
8.          v[j] = v[j+gap];
   
9.          v[j+gap] = temp;
   
10.       }
    
11. }

复制代码

看来我的水平离裸敲代码还差得不少

以后我会注意编译成功后才放代码。

谢谢LS

感觉是不是把每类帖最下面加上其他类贴的连接比较好？这样找起来也方便一点……

ps:我猜最后两篇里有一篇是heap sorting