希尔排序

希尔排序是插入排序的一种, 又称"缩小增量排序", 是插入排序算法的一种更高效的改进版本

原理:
    1、选定一个增长量h，按照增长量h作为数据分组的数据, 对数据进行分组
    2、对分好组的每一组数据完成插入排序
    3 减小增长量, 最小减为1, 重复第二步操作

增长量h的确定: 增长量h的值每一固定的规则, 采用以下规则: 
int h = 1;
while (h < 数组的长度 / 2) {
    h = 2 * h + 1；
}
// 循环结束后我们就可以确定h的最大值
h 的减小规则为:
    h = h / 2;

实现类

public class Shell {

    /**
     * 对数据a中的元素进行选希尔序
     *
     * @param a
     */
    public static void sort(Comparable[] a) {
        // 1、根据数组a的长度, 确定增长量h的初始值
        int h = 1;
        while (h < a.length / 2) {
            h = 2 * h + 1;
        }

        // 2、希尔排序
        while (h >= 1) {
            // 排序
            // 2.1、找到待插入的元素
            for (int i = h; i < a.length; i++) {
                // 2.2、把待插入的元素插入到有序数组中
                for (int j = i; j >= h; j -= h) {
                    // 待插入的元素a[j],比较a[j]和a[j - h]
                    if (greater(a[j - h], a[j])) {
                        // 交换元素
                        exchange(a, j - h, j);
                    } else {
                        // 待插入元素已经找到了合适的位置, 结束循环
                        break;
                    }
                }
            }
            // 减小h的值
            h = h / 2;
        }

    }

    /**
     * 比较v元素是否大于w元素
     *
     * @param v
     * @param w
     * @return
     */
    private static boolean greater(Comparable v, Comparable w) {
        return v.compareTo(w) > 0;
    }

    /**
     * 数据元素i和j交换位置
     *
     * @param a
     * @param i
     * @param j
     */
    private static void exchange(Comparable[] a, int i, int j) {
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

}

测试类

public static void main(String[] args) {
    Integer[] a = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
    Shell.sort(a);
    // 期望值: [1, 2, 3, 4, 5, 5, 6, 7, 8, 9]
    System.out.println(Arrays.toString(a));
}