希尔排序 Shell Sort 是插入排序的一种 
又称 缩小增量排序 Diminishing Increment Sort 
是直接插入排序的改进版本 ,非稳定排序算法
因 D.L.Shell 于 1959 年提出而得名

将一个原序列分成几个子序列，对每个子序列都进行一次插入排序
将原序列进行处理 使其变得有序一些
插入排序  O(n^2) 
越是有序的序列，需要的时间越少，甚至在某些情况下可以逼近O(n) 

首先将间隔 gap 设定为n/2，然后跳跃进行插入排序
再来间隔n/4，跳跃进行排序动作 
继续 间隔 n/8  n/16 ...  直到间隔为1  
由于上一次的排序动作将固定间隔内的元素排序好
间隔越来越小时，越来越有序 

3,2,1,9,4,8,7,5,6

gap=4
3 2 1 5 4 8 7 9 6 
gap=2
1 2 3 5 4 8 6 9 7 
gap=1
1 2 3 4 5 6 7 8 9 


public class ShellSort {
    public static void main(String[] args) throws Exception {
        int[] arr = { 3, 2, 1, 9, 4, 8, 7, 5, 6 };
        shellSort(arr);
    }

    private static void shellSort(int[] arr) {
        final int N = arr.length;
        int gap = N / 2;
        int i, j;
        while (gap > 0) {
            for (i = 0; i < gap; i++) {
                for (j = i + gap; j < N; j += gap) {
                    for (int k = j - gap; k >= i; k -= gap) {
                        if (arr[k] > arr[gap + k]) {
                            swap(arr, k, gap + k);
                        }
                        
                    }
                }
            }
            // for debug
            System.out.println("gap=" + gap);
            printArr(arr);
            gap /= 2;
        }
    }

    private static void printArr(int[] arr) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i]).append(" ");
        }
        System.out.println(sb.toString());
    }

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

https://gitee.com/dyyx/hellocode/blob/master/src/algo/sort/ShellSort.java


  冒泡选择和插入排序比较