希尔排序图解

        我们已经知道了冒泡排序法以及插入排序法。回顾一下原理。

        冒泡排序：把相邻的2元素进行比较后交换的操作。用的是交换元素。

        插入排序：把待插入的元素插入到对应的位置，其他元素要进行对应的后移(前移)。用到的思想是移动法。

        那么希尔排序就是在这2种思想的基础上改进。

图解：

代码实现: 

       冒泡方式：

public static void shellSort(int array[]){
        int temp = 0;
        //第一轮排序：结果应该是
        //第一轮是把这10个数据分成 10/2 = 5组
//        for (int i = 5; i < array.length; i++) {
//            //遍历各组中的所有元素(一共5组，每一组有2个元素),步长是5
//            for (int j = i - 5; j >= 0 ; j -= 5) {
//                //如果当前这个元素大于加上步长后的那个元素，就要交换
//                if (array[j] > array[j+5]){
//                    temp = array[j];
//                    array[j] = array[j+5];
//                    array[j+5] = temp;
//                }
//            }
//        }
//        System.out.println("第一轮结果是：" + Arrays.toString(array));
//
//        //第二轮是把这10个数据分成 5/2 = 2组
//        for (int i = 2; i < array.length; i++) {
//            //遍历各组中的所有元素(一共5组，每一组有2个元素),步长是5
//            for (int j = i - 2; j >= 0 ; j -= 2) {
//                //如果当前这个元素大于加上步长后的那个元素，就要交换
//                if (array[j] > array[j+2]){
//                    temp = array[j];
//                    array[j] = array[j+2];
//                    array[j+2] = temp;
//                }
//            }
//        }
//        System.out.println("第二轮结果是：" + Arrays.toString(array));
//
//        //第三轮是把这10个数据分成 2/2 = 1组
//        for (int i = 1; i < array.length; i++) {
//            //遍历各组中的所有元素(一共5组，每一组有2个元素),步长是5
//            for (int j = i - 1; j >= 0 ; j -= 1) {
//                //如果当前这个元素大于加上步长后的那个元素，就要交换
//                if (array[j] > array[j+1]){
//                    temp = array[j];
//                    array[j] = array[j+1];
//                    array[j+1] = temp;
//                }
//            }
//        }
//        System.out.println("第三轮结果是：" + Arrays.toString(array));

        //整合到一个算法中：
        //一共要进行几轮？array.length一直整除2，直到等于1，中间进行的轮次
        //第1轮怎么排？for (int i = array.length/2; i < array.length; i++) 、for (int j = i - array.length/2; j >= 0 ; j -= array.length/2)
        //第2轮怎么排？for (int i = array.length/2/2; i < array.length; i++) 、for (int j = i - array.length/2/2; j >= 0 ; j -= array.length/2/2)...
        int num = array.length/2;
        while (num >= 1){
            for (int i = num; i < array.length; i++) {
                for (int j = i - num; j >= 0 ; j -= num) {
                    //如果当前这个元素大于加上步长后的那个元素，就要交换
                    if (array[j] > array[j+num]){
                        temp = array[j];
                        array[j] = array[j+num];
                        array[j+num] = temp;
                    }
                }
            }
            System.out.println(Arrays.toString(array));
            //进行完此轮后num继续除以2
            num = num/2;
        }
    }

        插入方式：

 public static void shellSort2(int array[]){
        int num = array.length/2;
        while (num >= 1){
            for (int i = num; i < array.length; i++) {
                int targetIndex = i - num;
                int target = array[i];
                while (targetIndex >= 0 && array[targetIndex] > target){
                    array[targetIndex+num] = array[targetIndex];
                    targetIndex -= num;
                }
                array[targetIndex + num] = target;
            }
            System.out.println(Arrays.toString(array));
            //进行完此轮后num继续除以2
            num = num/2;
        }
    }