hsp 希尔排序 63-65

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    public static void main(String args[]) {

        int[] arr = new int[7];
        Scanner scanner = new Scanner(System.in);

        for(int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }

        // insertSort(arr);
        shellSort(arr);
    }


    public static void insertSort(int[] arr) {

        for(int i = 1; i < arr.length; i++) {

            int insertVal = arr[i];
            int insertIndex = i - 1;

            //待插入的值小于有序那部分中最大的值时，才需要移位，如果大于等于的话，不动就好了
            if(insertVal < arr[insertIndex]) {
                //找insertVal插入位置的前一个索引
                while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
                    arr[insertIndex + 1] = arr[insertIndex];
                    insertIndex--;
                }
            }    
            arr[insertIndex + 1] = insertVal;

            System.out.println("第" + i + "轮插入后");
            System.out.println(Arrays.toString(arr));
        }

    }


    public static void shellSort(int[] arr) {

        int count = 0;

        for(int gap = arr.length / 2; gap > 0; gap /= 2) {
            //从第gap个元素，逐个对其所在的组进行简单插入排序
            for(int i = gap; i < arr.length; i++) {
                int insertVal = arr[i];
                int insertIndex = i - gap;

                if(insertVal < arr[insertIndex]) {

                    while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
                        arr[insertIndex + gap] = arr[insertIndex];
                        insertIndex -= gap;
                    }
                }

                arr[insertIndex + gap] = insertVal;
                // System.out.println("第" + (++count) + "轮排序后");
                // System.out.println(Arrays.toString(arr));
            }

            System.out.println("第" + (++count) + "轮排序后");
                System.out.println(Arrays.toString(arr));
        }
    }

}