希尔排序（Shell Sort） O(n^(1.3))

介绍

希尔排序是简单插入排序的改进版，是插入排序的一种，又称为 “缩小增量排序”,希尔排序是把数列按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个数列恰被分成一组，算法便终止。希尔排序的主要性能由增量控制，常用（gap/2）作为增量计算方式，除此之外还有一些常用增量，如：`Hibbard 增量序列`,`Knuth 增量序列`,`Gonnet 增量序列` ,`Sedgewick 增量序列` 等

算法描述

• 选择一个增量序列ti，tk，…，tk，其中ti>tj，tk=1；（如：1，3，7，15，31....）
• 按增量序列个数k，对序列进行k 趟排序；
• 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子序列进行直接插入排序。当增量为1 时，整个序列作为一个序列来处理，序列长度即为整个序列的长度。

稳定性

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的

Hibbard增量序列

Hibbard 增量序列的通项公式为：
hi=2^i−1 i = log2(h+1)
Hibbard 增量序列的递推公式为：
h1=1,hi=2∗h(i−1)+1 => h(i-1) = h(i)>>1
Hibbard 增量序列的最坏时间复杂度为 Θ(N^(3/2))；平均时间复杂度约为 O(N^(5/4))

动图展示

shellSort.gif

代码实现

public class ShellSort {

    public static void main(String[] args) {
        int[] arrays = new int[]{27, 6, 27, 42, 23, 15, 38, 50, 35, 14, 40, 28, 29};
        print(arrays);
        int[] res = shellSort(arrays);
        print(res);
    }

    private static int[] shellSort(int[] arr) {
        int len = arr.length;
        if (len <= 1) {
            return arr;
        }
        int gap = initFirstIncremental(len);
        while (gap > 0) {
            for (int i = 0; i < len; i++) {
                if (i + gap < len && arr[i] > arr[i + gap]) {
                    swap(arr, i, i + gap);
                }
            }
            print(arr);
            gap >>= 1;
        }
        return arr;
    }

    //初始化第一个增量
    //1  3  7  15  31  63
    private static int initFirstIncremental(long size) {
        long i = 1;
        while ((1L << i) - 1 <= size) {
            i |= i << 1L;
        }
        return (int) i >> 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static void print(int[] arr) {
        for (int i : arr) {
            System.out.print(i + "\t");
        }
        System.out.println();
    }
}