希尔排序

希尔排序

如果上一篇初级排序算法中的插入排序你已经熟悉，那么今天的这个希尔排序对你来说就要简单一些。希尔排序，就是使用不同增量进行一遍一遍的插入排序的排序算法。首先，增量是什么？希尔排序的思想就是使数组中任意间隔为h的元素都要有序，间隔h就是增量，之所以叫他增量，是因为他是在不断变化的。

public class ShellSort {
    public static void sort(int[] array){
        int N = array.length;
        int h = 1;
        while (h<N/3)h=3*h+1;//1,4,13,40,121,364.....//增量序列
        while (h>=1){
            for (int i = h;i<N;i++){
                for (int j = i;j>=h&&array[j]<array[j-h];j-=h){
                    int temp = array[j];
                    array[j] = array[j-h];
                    array[j-h] = temp;
                }
              } 
              h=h/3;
        }
    }
}

可以看到代码中h在第一个while循环处确定了初值，在第二个while循环中一点一点减小，直到减为1，排序完成。第二个while循环中还有两个for循环，这两个for循环完成的就是间隔为h的插入排序。第一个for循环的i从h移动到N，然后改变h的值再次循环，直到h减为1。第二个for循环中就是比较array[j]和array[j-h]的大小，如果array[j]>array[j-h]那么停止这次循环；反之，则进行交换。插入排序中比较的是array[j]和array[j-1]，所以说，希尔排序就是使用不同增量的插入排序算法。当然，也由于希尔排序可以使用不同增量，于是透彻的理解希尔排序的性能仍旧是个巨大的挑战。今天我们代码中使用的是1,24,13,40,121,364…这一个增量序列，其实，还有其他别的增量序列可以供我们选择,比如1,2,4,8,16….. 也许有人不理解为什么要间隔h，为什么要使用这个递增序列？速度确实可以提升吗？实验数据告诉我们，是的！希尔排序比之前初级排序算法中的排序算法都要快，并且，数组越大，优势越大。但为什么呢？从数学方面的证明还是等专家们去做吧，我只能举个栗子。比如有一个特别长的整型数组，特别小的数排在了最后边，插入排序的话它就需要一点一点的挪到前面，而希尔排序则是跳过来的，一次跳多远呢？