[算法]希尔排序法

希尔排序，shell sort是基于插入排序的一种改进

相对这种算法来说，最经济实惠的就是拿例子来说事，直接实战，比什么都管用。好，既然这样，那我们就直接对数组[6，2，4，1，5，9]来进行排序。

第一步，我们就是要选取关键字，像我们这个待处理数组元素为6，所以我们采用6/2=3，所以关键字就是3.

所以可将该数据分为三部分，分别是

然后我们分别对该三组数据内部进行插入排序，得到结果

还原数组格式：[1，2，4，6，5，9]

第二趟，选取关键字3/2=1，所以关键字为1.所以我们又要对[1，2，4，6，5，9]进行如上处理，但是由于关键字是1，所以，是不是没有必要了，那我们就要对该数组直接进行最后的插入排序了。

还记得插入排序怎么排吗?

 [1 ，2，4]都不用动,过程省略,到5的时候,将5取出,在前边的有序数组里找到适合它的位置插入,就是4后边,6前边，后边的也不用改,所以排序完毕

得到结果：

               [1，2，4，5，6，9]

那我们用图来说明一下：

因为在操作a中，6比1大，所以6和1互换位置，而另外两组当中，顺序是正确的，所以既不用动了。就是这样。

代码展示：

public class Test {
 
//   /**
//    * @param args the command line arguments
//    */
   static void shell_sort(int[] unsorted, int len)
       {
           int group, i, j, temp;
           for (group = len / 2; group > 0; group /= 2)
           {
                for (i = group; i < len;i++)
                {
                    for (j = i - group; j >=0; j -= group)
                    {
                        if (unsorted[j] >unsorted[j + group])
                        {
                            temp = unsorted[j];
                            unsorted[j] =unsorted[j + group];
                            unsorted[j + group]= temp;
                        }
                   }
                }
           }
       }
       public static void main(String[] args)
       {
           int[] x = { 6, 2, 4, 1, 5, 9 };
           shell_sort(x, x.length);
           for(int item:x)
           {
               System.out.print(item+", ");
           }
           System.out.println();
       }
}
 

   运行结果：

 

相信大家能看明白的！

     其次，我想说的是如何选取关键字，因为除了这个环节，其他环节基本上就是插入排序了。那如何选取关键字呢？

我得到的结论是：n/2

所以了，如果是10个数，该如何去关键字呢？15个数呢？

当10个数的时候，10/2=5，5/2=2，2/2=1，所以，关键字依次为5，2，1

当15个数的时候，15/2=7，7/2=3，3/2=1，所以关键字依次为：7，3，1

小结：

       很简单吧，个人认为，整个希尔排序，既是对插入排序的优化，插入排序搞明白了，希尔排序里的关键就是关键字的选取，别的就没有什么了