经典排序算法——希尔排序

注：本文参考https://www.cnblogs.com/chengxiao/p/6104371.html 

希尔排序原理

在讲解希尔排序之前，我们有必要先回头看一下插入排序的问题。插入排序不管数组分布时怎么样的，都是一步步的对元素进行比较，移动，插入。比如[5,4,3,2,1,0]这种倒序序列，数组末端的0要回到首位很费劲，比较和移动元素均需n-1次。这时就引出了希尔排序。

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的更高效的版本。该算法是突破O(n^2)的第一批算法之一。

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

图解希尔排序

我们来看下希尔排序的基本步骤，我们选择增量gap = length/2，缩小增量继续以gap = gap/2 的方式，这种增量选择我们可以用一个序列来表示,{n/2,(n/2)/2...1}的增量序列。

原始数组 以下数据元素颜色相同的为一组

初始增量 gap = length/2 = 5，所以整个数组被分为5组，即从第一位置的数字开始向后+n*gap为同一组，所以第一次增量后5组为[8,3],[9,5],[1,4],[7,6],[2,0]

对这五组分别进行插入排序，例如[8,3]插入排序后会交换位置[3,8]，[9,5]插入排序后会交换位置为[5,9]等等。所以执行后会将小的数字放在数组的前面。

然后继续减小增量gap=5/2 = 2，数组被分为2组，即从第一位置的数字开始向后+n*gap为同一组,搜衣第二次增量后2组为[3,1,0,9,7] 和 [5,6,8,4,2]。如下图所示

对以上两组再分别进行插入排序，在[3,1,0,9,7]中会变为[0,1,3,7,9]， [5,6,8,4,2]会变为[2,4,5,6,8]，如下图所示，可以看到整个数组的有序程度更进一步了。

再缩小增来gap=2/2 = 1 ，此时整个数组为1组[0,2,1,4,3,5,7,6,9,8]，如下图所示

  　经过上面的“宏观调控”，整个数组已经基本有序。此时再对整个数组进行插入排序，只需进行少量的交换即可变为有序数组。

代码实现

1.交换式实现方式

/**
     * 交换式排序
     * @param array
     */
public static void sort1(int[] array){
        int temp = 0;
        int count = 0;
        for(int gap=array.length/2; gap >0; gap /= 2){
            for (int i = gap; i < array.length; i++) {
                int j = i - gap;
                while (j >=0 && array[j] > array[j+gap]){
                    //所在分组需做交换
                    temp = array[j];
                    array[j] = array[j+gap];
                    array[j+gap] = temp;
                    j -= gap;
                }
            }
        }
    }

2.移位式实现方式

/**
     * 移位式排序
     * @param array
     */
public static void sort2(int[] array){
        for(int gap = array.length/2; gap > 0; gap /= 2){
            for(int i=gap; i< array.length; i++) {
                int insertValue = array[i];
                int insertIndex = i - gap;
                int startIndex = insertIndex;
                while (insertIndex >= 0 && insertValue < array[insertIndex]) {
                    //所在分组需做后移
                    array[insertIndex + gap] = array[insertIndex];
                    insertIndex -= gap;
                }
                if(insertIndex != startIndex){
                    array[insertIndex + gap] = insertValue;
                }
            }
        }
    }

代码分析

1）第一层for循环用于确定分组大小，这里选用对数组大小减半的的方式，后面每次对原分组减半，直到分组大小为1

2）第二层for循环表示从第gap个元素开始(这里说明下为什么从第gap个元素开始：第gap个元素刚好为分组中的第一组的第二个元素，因为我们的插入排序为从第二个元素开始向前比较)，向后依次执行插入排序，直到最后一个元素

3）while循环用于对每个分组进行插入排序(交换式为当找到比插入元素大的元素时，交换两个元素。移位式为当找到比插入元素大时，将那个元素向后移动gap位，最后再将待插入元素放在空缺的位置即可)

时间复杂度

从我们的分析可知，希尔排序中对于增量序列的选择十分重要，直接影响到希尔排序的性能。我们上面选择的增量序列{n/2,(n/2)/2...1}，其最坏时间复杂度依然位O(n^2)，一些经过优化的增量序列如Hibbard经过复杂证明可使得最坏时间复杂度为O(n^3/2)。

测试算法执行效率

与前面的排序算法相同，我们依然生成10万个随机数的数组，使用插入排序方法进行排序，看其执行时间。测试代码如下

public static void main(String []args){
        int[] array = new int[1000000];
        for (int i = 0; i < 1000000; i++) {
            array[i] = (int) (Math.random() * 8000000);
        }
        long begin = System.currentTimeMillis();
        sort2(array);
        System.out.println("总耗时="+(System.currentTimeMillis()- begin));
}

测试结果

可以看到希尔排序算法比插入排序更快，10万个数据的数组排序大概需要300多毫秒时间。下篇我们将介绍快速排序算法，排序效率是否会更高呢？一起期待！

总结

希尔排序是一个基于插入排序的算法，解决了当待排序数组倒序时使用插入排序算法要移动多次的耗时操作。希尔排序的核心算法为先将待排序数组进行分组进行小范围的排序，每次分组排序后待排序数组就会在大范围上更有序。当分组大小减小到1时，待排序数组已经基本有序，此时再执行插入排序，可以确保移动或交换的次数更少，从而达到提升排序效率的目的。

注：本文参考https://www.cnblogs.com/chengxiao/p/6104371.html