排序----希尔排序

上一篇：插入排序

希尔排序的思想是：使数组中任意间隔为h的元素都是有序的。这样的数组成为h有序数组。换句话说，一个h数组就是h个互相独立的有序数组 编织在一起组成的数组。

实现希尔排序的一种方法是对于每个h,使用插入排序将h个子数组独立地排序。然后按某种次序递减h,可以实现数组整体排序。这里出现两个问题：为什么使用插入排序而不是选择排序？按哪种次序递减h?

不适用选择排序的原因是选择排序前一次的遍历对后一次的遍历不提供任何信息，所以h从大减小毫无用处；虽然还没有理论支持，但按1/3递减h有着很好的效率。

希尔排序是对直接插入排序的改进，它权衡了子数组的规模和有序性。它避免了直接插入排序主键最小的元素正好在数组的尽头，要将它挪动到正确的位置需要移动次数很多的问题。

希尔排序的算法性能不仅取决于h,还取决于h之间的数学性质，比如它们的公因子等。

希尔排序的用时是次平方级别的，目前发现希尔排序最坏情况也达不到平方级别，是N^1.5次方。

public class Shell {
    public static void sort(Comparable[] a){
        int N = a.length;
        int h = 1;
        while(h<N/3)h = 3*h+1;//1,4,13,40,121,......将h按此规律递减
        while(h>=1){
            for(int i = 1;i<N;i++) //这里和插入排序一摸一样
                for(int j=i;j>0&&less(a[j],a[j-1]);j--)
                    exch(a,j,j-1);
            h = h/3;
        }
    }
    //less()、exch()、isSorted()、main()方法见“排序算法模板”
}

从希尔排序可以发现，我们对插入排序稍微改动，就在效率上取得了极大的提升，算法的魅力正在于此。

下一篇：归并排序