插入排序和希尔排序（Java）

插入排序思想：开始时指针指向第二个元素，从指针位置往前进行元素比较，大的元素往后挪一位，直到找到比指针位置元素小的位置，将该位置赋值成指针指向的值，指针往后移一位，此时前面的元素都已经排好序了，往复元素比较操作，只需要找到插入的位置即可
实现代码：

    /**
     * 插入排序
     *
     * @param nums
     */
    public void insertSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int target = nums[i];
            int j = i;
            for (; j > 0 && target < nums[j - 1]; j--) {//大的往后挪
                nums[j] = nums[j - 1];
            }
            
            //小的位置赋值成插入值
            nums[j] = target;
        }
    }

希尔排序：观察插入排序发现如果数组已经有一定的排列了，那么插入排序性能会很高，例：0 2 3 4 1 排序，前面都是一次判断，不需要交换操作，只有最后一次循环将 2 3 4 往后挪一位，将 1 插入 0 后面。
希尔排序加入了步长，而不是一开始就从头进行插入排序，目的是将数组进行一定的排序，最后再用插入排序进行排序，性能比直接使用插入排序快

shellSort.png

实现代码：

    /**
     * 希尔排序
     *
     * @param nums
     * @param step 步长
     */
    public void shellSort(int[] nums, int step) {
        for (int start = 0; start < step; start++) {//以步长为单位滚动数组
            for (int i = step + start; i < nums.length; i += step) {
                int target = nums[i];//获取插入的元素:索引是step + start
                int j = i;
                // 从后面往前遍历的条件 改成 step - 1 了
                for (; j > step - 1 && target < nums[j - step]; j -= step) {//前面元素大的往后挪
                    nums[j] = nums[j - step];
                }

                //小的位置赋值成插入值
                nums[j] = target;
            }
        }
    }

为了对比直接插入排序和希尔排序的区别，我加入了一个变量来计数挪位操作的次数

    /**
     * 希尔排序
     *
     * @param nums
     * @param step 步长
     */
    public void shellSort(int[] nums, int step, int[] count) {
        for (int start = 0; start < step; start++) {//以步长为单位滚动数组
            for (int i = step + start; i < nums.length; i += step) {
                int target = nums[i];//获取插入的元素:索引是step + start
                int j = i;
                // 从后面往前遍历的条件 改成 step - 1 了
                for (; j > step - 1 && target < nums[j - step]; j -= step) {//前面元素大的往后挪
                    nums[j] = nums[j - step];
                    count[0]++;
                }

                //小的位置赋值成插入值
                nums[j] = target;
            }
        }
    }

测试代码：

        int[] nums = new int[]{5, 7, 1, 3, 9, 0, 1, 6, 8, 4};
        int[] count = new int[1];
        shellSort(nums, 1, count);
        for (int i : nums) {
            System.out.print(i + " ");
        }
        System.out.println();
        System.out.println("插入排序交换次数：" + count[0]);

        nums = new int[]{5, 7, 1, 3, 9, 0, 1, 6, 8, 4};
        count = new int[1];
        shellSort(nums, 4, count);
        shellSort(nums, 1, count);
        for (int i : nums) {
            System.out.print(i + " ");
        }
        System.out.println();
        System.out.println("以步长4先进行希尔排序后排序的交换次数：" + count[0]);

结果：
0 1 1 3 4 5 6 7 8 9
插入排序交换次数：21
0 1 1 3 4 5 6 7 8 9
以步长4先进行希尔排序后排序的交换次数：15