博客

希尔排序

希尔排序作为插入排序的一种。也称缩小增量排序，是直接插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰好分成一组，算法便终止。 

过程

希尔排序是基于插入排序的以下两点性质而提出改进方法的;
1. 插入排序在对几乎已经排序好的数据操作时，效率高，即可达到线性排序的效率。
2. 但插入排序一般是比较低效的，因为插入排序每次只能将数据移动一位。

基本思想

取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量，即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法，比较相隔较远距离的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。算法先将一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数分成一组，排序完成。
一般初次取序列的一半为增量，以后每次减半，直到增量为1.
给定实例的shell排序的排序过程：
假设待排序文件有10个记录，其关键字分别是：
49，38，65，97，76，13，27，49，55，4；
增量序列的取值依次为：
5，2，1

稳定性

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变形同元素的相对顺序，但在不同的插入排序过程中，相同的元素的可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

排序过程

缩小增量
希尔排序属于插入类排序，是将整个有序序列分割成若干小的子序列分别进行插入排序
排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作，直至di=1，即所有记录放进一个组中排序为止。

到了这有一个问题摆在大家面前了，也就是说一开始这个间隔应该取多少比较好呢？这里有一个公式：

上面10条数据，所以第一个增量是5。

还有一种计算的方式是这样的：增量的初始值是1，通过3*h+1循环计算，一直得到h刚好不大于数组长度。此时就取h做最大间隔。然后继续通过h=(h-1)/3来计算剩下的增量。

代码

    public static void shellSort(int[] array){
        int number = array.length / 2;
        int i;
        int j;
        int temp;
        while (number >= 1){
            for(i = number; i<array.length; i++){
                temp = array[i];
                j = i - number;
                while (j >= 0 && array[j] < temp){
                    array[j + number] = array[j];
                    j = j - number;
                }
                array[j + number] = temp;
            }
            number = number / 2;
        }
    }


    public static void shellSort2(int[] array){
        int N = array.length;
        for(int gap = N/2; gap > 0; gap /= 2){
            for(int i = gap; i<N; i++){
                insertI(array,gap,i);
            }
        }
    }

    private static void insertI(int[] arr,int gap, int i){
        int inserted = arr[i];
        int j;
        for(j = i-gap; j>=0 && inserted < arr[j]; j -= gap){
            arr[j+gap] = arr[j];
        }
        arr[j+gap] = inserted;
    }

优化

总结

最佳情况：T(n) = O(nlogn)。最坏情况：T(n) = O(n)。平均情况：T(n) = O(nlogn)。

希尔排序为什么这么有名气，是因为它是第一批突破o(n)的排序算法之一。如有问题还请指正。