排序--希尔排序

版权声明：本文源自简书tianma，转载请务必注明出处：http://www.jianshu.com/p/d3a12239d376

概念

希尔排序是插入类排序算法，它的本质就是分组插入排序，它采取分割策略：将相距某个“增量”的记录组成一个子序列，保证在每个子序列内部分别进行插入排序后得到的结果是基本有序。

该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比插入排序有大幅度提高。

Java实现

// 定义接口
interface Sorter {
    /**
     * 将数组按升序排序
     */
    int[] sort(int[] arr);

    /**
     * 交换数组arr中的第i个位置和第j个位置的关键字
     */
    default void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
//希尔排序
public class ShellSorter implements Sorter {

    @Override
    public int[] sort(int[] arr) {
        shellSort(arr);
        return arr;
    }

    // Shell排序的关键就是增量序列的选取：
    // 增量序列原则： 增量序列的最后一个增量必须等于1
    private void shellSort(int[] arr) {
        int len = arr.length;
        int increment = len;
        for (; increment != 1;) {// 循环直至increment=1
            increment = increment / 3 + 1; // 计算增量序列(将整个序列分成increment组,在组内进行插入排序)
            for (int i = increment; i < len; i++) {
                if (arr[i] < arr[i - increment]) {
                    int tmp = arr[i]; // 暂存arr[i]的值
                    int j;
                    for (j = i - increment; j >= 0 && tmp < arr[j]; j -= increment) {
                        // 组内记录后移,查找插入位置
                        arr[j + increment] = arr[j];
                    }
                    // 找到插入位置
                    arr[j + increment] = tmp;
                }
            }
        }
    }
}

演示

比如我们待排序的数组是 {9, 1, 5, 8, 3, 7, 4, 6, 2}
初始时increment=arr.length=9，increment != 1，执行第1次循环：
increment = 9/3+1 = 4，将整个序列分成4组，组内进行插入排序：

第 1 组： 9 3 2    -----------> 2 3 9
第 2 组： 1 7      -----------> 1 7
第 3 组： 5 4      -----------> 4 5
第 4 组： 8 6      -----------> 6 8

此时序列为 2 1 4 6 3 7 5 8 9

increment=4，increment != 1，执行第2次循环：
increment = 4/3+1 = 2，将整个序列分成2组，组内进行插入排序：

第 1 组： 2 4 3 5 9    ----------->  2 3 4 5 9
第 2 组： 1 6 7 8      ----------->  1 6 7 8

此时序列为 2 1 3 6 4 7 5 8 9

increment=2，increment != 1，执行第3次循环：
increment = 2/3+1 = 1，将整个序列分成1组，组内进行插入排序（演变为直接插入排序）：

第 1 组 ： 2 1 3 6 4 7 5 8 9  -----------> 1 2 3 4 5 6 7 8 9

increment=1，结束循环，排序完毕。