希尔排序思想与实现

希尔排序是对插入排序的修改，我们知道插入排序比选择排序更优，希尔排序又是比插入排序更优的一种方式，具体原因，看完下面的思想就知晓。

插入排序是拿出无序队列中的第一个元素与有序队列进行比较，通过多次相邻交换插入到相应的位置。希尔排序改变了交换的两个元素之间的距离，与插入排序的相邻交换不同，希尔排序交换距离为h的元素，最终变成h有序数组（间隔为h的元素组成一个有序数组，原数组由h个有序数组组成），不断缩小h的值，当h最终变为1，就实现了原数组的排序。希尔排序增大了交换的跨度，所以减少了交换的次数，加快了排序的速度，另一方面因为不断减小h，增大了比较的次数。
h有序数组的举例：
h=3的序列1，6，11，2，7，12，3，8，13，4，9，14，5，10，15
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15

例：1, 4, 10, 5, 4, 9, 12, 2
初始值h=3

h=3
分三组
1, 5, 12
4， 4， 2
10， 9
对每组进行比较交换
1, 5, 12
2, 4, 4
9, 10
所得3有序数组1，2，9，5，4，10，12，4

h=2
分两组
1, 9, 4, 12
2, 5 10 4
对每组进行比较交换
1, 4, 9, 12
2, 4, 5, 10
所得2有序数组1，2，4，4，9，5，12，10

h=1
分一组
1，2，4，4，9，5，12，10
对该组比较交换
1，2，4，4，5，9，10，12
所得1有序数组1，2，4，4，5，9，10，12

最终希尔排序结果1，2，4，4，5，9，10，12

最后一次排序与插入排序算法相同，但是毋庸置疑交换次数减少了，加快了排序速度，数组长度越大，越能体现出希尔排序的优势。

实现代码

/**
 * 希尔排序:依次改变缩量的插入排序
 * 
 * @see 重复做的事：改变缩量，从无序序列中选择第一个元素，与有序序列交换位置，与有序序列比较
 * @param a
 */
public static void shellSort(int[] a) {
    int h = 1;
    // 根据条件获取最大h
    while (h < a.length / 3) {
        h = h * 3;
    }
    // 缩小h并重复排序算法
    while (h >= 1) {
        // 拿出h之后的元素作为插入元素
        for (int i = h; i < a.length; i++) {
            // 与前面h个位置的元素交换位置直到找到一个小于当前值的元素
            for (int j = i; j >= h; j -= h) {
                if (a[j] < a[j - h]) {
                    int temp = a[j];
                    a[j] = a[j - h];
                    a[j - h] = temp;
                } else {
                    break;
                }
            }
        }
        h = h / 3;
    }
}

扩展文章
快速排序思想与实现
常用四种排序算法的思想与实现