【图解】希尔排序

 private static void shellSort(int[] arr) {
        int length = arr.length;
        //进行分组，最开始时的增量（gap）为数组的一半
        for (int gap = length / 2; gap > 0; gap /= 2) {
            //对各个分组进行插入排序
            for (int i = gap; i < length; i++) {
                insertI(arr, gap, i);
            }
        }
    }

    /**
     * 将arr[i]插入到所在分组的正确位置上
     * arr[i]所在分组为：
     * ... arr[i-2gap],arr[i-gap],arr[i],arr[i+gap],arr[i+2gap]...
     */
    private static void insertI(int[] arr, int gap, int i) {
        int inserted = arr[i];
        int j;
        //插入的时候按组进行插入，组内元素两两相隔gap
        for (j = i - gap; j >= 0 && inserted < arr[j]; j -= gap) {
            arr[j + gap] = arr[j];
        }
        arr[j + gap] = inserted;
    }