算法渣-排序-希尔

希尔 排序 是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一

算法

直接插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，比如[5,4,3,2,1,0]这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次

是否能够减少这样的移位呢？不希望是一步一步的移动，而是大步大步的移动。

希尔排序是把记录按下标的一定 增量分组 ，对每组使用直接插入 排序算法 排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

初始时,有一个大小为 10 的无序序列

在第一趟排序中,我们不妨设 gap1 = N / 2 = 5,即相隔距离为 5 的元素组成一组,可以分为 5 组

接下来,按照直接插入排序的方法对每个组进行排序

在第二趟排序中,我们把上次的 gap 缩小一半,即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组,可以分为 2 组

按照直接插入排序的方法对每个组进行排序

在第三趟排序中,再次把 gap 缩小一半,即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组,即只有一组

按照直接插入排序的方法对每个组进行排序。此时,排序已经结束

演示

• 1.增量N/2=4分组

{35, 14}, {33, 19}, {42, 27} , {10, 44}

排序完：

• 2.增量N/2/2=2分组

{14, 27, 35, 42}, {19, 10, 33, 44}

排序完：

• 3.增量N/2/2/2=1分组排序

也可以通过动画更清晰了解整个排序过程

动画： http://www.zhuxingsheng.com/tools/sort/sort.html

分组排序后，他们的索引还是保留在原始索引中，来两个更加直观的动画演示

实现

static void shellSort(int []array) {
        //以length/2为增量
        for (int gap=array.length/2;gap>0;gap= gap/2) {
            //以gap分组，进行排序
           for(int i = gap;i<array.length;i++){
               int tmp = array[i];
               int j = i - gap;
               //相对直接插入，步长从1变成了gap
               while ( j>=0 && tmp<array[j] ) {
                   array[j+gap] = array[j];
                   j=j-gap;
               }
               array[j+gap] = tmp;
           }
        }
    }

复杂度

希尔排序的时间复杂度与增量(即，步长gap)的选取有关

{1,2,4,8,…}这种序列并不是很好的增量序列，使用这个增量序列的时间复杂度（最坏情形）是O(n²)

Hibbard提出了另一个增量序列{1,3,7，…,2^k-1}，这种序列的时间复杂度(最坏情形)为O(n^1.5)

Sedgewick提出了几种增量序列，其最坏情形运行时间为O（n^1.3）,其中最好的一个序列是{1,5,19,41,109,…}

9×4^i−9×2i+1  和 4^i−3×2^i+1  这两个算式

其中， i=0,1,2,⋯ 时，第一个式子计算出的值分别为1，19，109，……； i=2,3,⋯ 时，第二个式子算出的值分别为5，41，……