【排序算法】4.希尔排序

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。
例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样(竖着的元素是步长组成)：
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我们对每列进行排序：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。这时10已经移至正确位置了，然后再以3为步长进行排序：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后变为：
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步长进行排序（此时就是简单的插入排序了）

排序分析图：

排序分析

java 实现：

public class ShellSortTest {
    public static void main(String[] args) {
        int[] input = new int[]{2,5,4,89,7,89,52,12,54,78};
        StopWatch stopWatch = new StopWatch("countTime");
        //1. 交换法时间希尔排序
        stopWatch.start();
        shellSortWithSwitch(input);
        PrintUtils.print(input);
        stopWatch.stop();

        int[] input2 = new int[]{2,5,4,89,7,89,52,12,54,78};
        //2. 插入法实现希尔排序
        stopWatch.start();
        shellSortWithInsertion(input2);
        PrintUtils.print(input);
        stopWatch.stop();

        System.out.println(stopWatch);
    }
    /**
     * 使用的希尔排序的缩小增量思想，但是用交换实现，交换频繁，效率低下
     * @param input
     */
    public static void shellSortWithSwitch(int[] input){
        for(int step = input.length/2; step > 0; step /= 2){
            for (int groupNum = 0; groupNum < step; groupNum++){
                //交换的方式实现
                for (int i = groupNum; i < input.length - step; i += step){
                    if (input[i] > input[i + step]){
                        int temp = input[i];
                        input[i] = input[i + step];
                        input[i + step] = temp;
                    }
                }
            }
        }

    }

    /**
     * 
     * @param input
     */
    public static void shellSortWithInsertion(int[] input){
        for(int step = input.length/2; step > 0; step /= 2){
            for (int groupNum = 0; groupNum < step; groupNum++){
                //用插入排序的方式实现
                for (int i = step + groupNum; i < input.length; i += step){
                    int temp = input[i];
                    boolean isInserted = false;
                    for (int tmp = i;tmp > groupNum;tmp-=step){
                        if (input[tmp-step] > temp){
                            input[tmp] = input[tmp-step];
                        }else {
                            input[tmp] = temp;
                            isInserted = true;
                            break;
                        }
                    }
                    if (!isInserted){
                        input[groupNum] = temp;
                    }
                }
            }
        }

    }
}

时间复杂度

• 最优时间复杂度：根据步长序列的不同而不同
• 最坏时间复杂度：O(n2)
• 稳定性：不稳定

我们程序实现的步长，{1,2,4,8,...}这种序列就是我们程序中实现的这种，并不是很好的增量序列，使用这个增量序列的时间复杂度(最坏情形)是O(n^2 )，Hibbard提出了另一个增量序列{1,3,7，...,2^k-1 }(质数增量)，这种序列的时间复杂度(最坏情形)为O(n^1.5 )，这个提高就很厉害了，只是修改一个算法的一个参数；Sedgewick提出了几种增量序列，其最坏情形运行时间为O(n^1.3 ),其中最好的一个序列是{1,5,19,41,109,...}，最后这个就当是科普小知识吧，因为给你你也不一定能用，请原谅我的直接，当别人说希尔排序的最坏时间复杂度是O(n^2 )的时候，你也可以给他们科普一下，希尔排序的最坏时间复杂度是可以做到O(n^1.3 )的。并不是很理解，先记着