/**
     * 推到的方式來演示每一步怎么做，然后找規(guī)律
     */
    @Test
    public void processDemo() {
        int arr[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        System.out.println("原始數(shù)組：" + Arrays.toString(arr));
        processShellSort(arr);
    }

    public void processShellSort(int[] arr) {
        // 按照筆記中的基本思想，一共三輪
        // 第 1 輪：初始數(shù)組 [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
        // 將 10 個(gè)數(shù)字分成了 5 組( length / 2)，增量也是 5，需要對(duì) 5 組進(jìn)行排序
        // 外層循環(huán)，并不是循環(huán) 5 次，只是這里巧合了。
        // 一定要記得，希爾排序：先分組，在對(duì)每組進(jìn)行插入排序
        for (int i = 5; i < arr.length; i++) {
            // 第 1 組：[8,3] , 分別對(duì)應(yīng)原始數(shù)組的下標(biāo) 0,5
            // 第 2 組：[9,5] , 分別對(duì)應(yīng)原始數(shù)組的下標(biāo) 1,6
            // ...
            // 內(nèi)層循環(huán)對(duì) 每一組 進(jìn)行直接排序操作
            // i = 5 ；j = 0, j-=5 = 0 - 5 = -5,跳出循環(huán)，arr[j] = 8 ，這是對(duì)第 1 組進(jìn)行插入排序
            // i = 6 ；j = 1, j-=5 = 1 - 5 = -4,跳出循環(huán)，arr[j] = 9 ， 這是對(duì)第 2 組進(jìn)行插入排序
            // i = 7 ；j = 2, j-=5 = 2 - 5 = -3,跳出循環(huán)，arr[j] = 1 ，這是對(duì)第 3 組進(jìn)行插入排序
            // i = 8 ；j = 3, j-=5 = 3 - 5 = -2,跳出循環(huán)，arr[j] = 7 ，這是對(duì)第 4 組進(jìn)行插入排序
            // i = 9 ；j = 4, j-=5 = 4 - 5 = -1,跳出循環(huán)，arr[j] = 2 ，這是對(duì)第 5 組進(jìn)行插入排序
            for (int j = i - 5; j >= 0; j -= 5) {
                // 如果當(dāng)前元素大于加上步長后的那個(gè)元素，就交換
                if (arr[j] > arr[j + 5]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 5];
                    arr[j + 5] = temp;
                }
            }
        }
        System.out.println("第 1 輪排序后：" + Arrays.toString(arr));

        // 第 2 輪：上一輪排序后的數(shù)組：[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
        // 將 10 個(gè)數(shù)字分成了 2 組（上一次的增量 5 / 2），增量也為 2，需要對(duì) 2 組進(jìn)行排序
        for (int i = 2; i < arr.length; i++) {
            // 第 1 組：[3,1,0,9,7] , 分別對(duì)應(yīng)原始數(shù)組的下標(biāo) 0,2,4,6,8
            // 第 2 組：[5,6,8,4,2] , 分別對(duì)應(yīng)原始數(shù)組的下標(biāo) 1,3,5,7,9

            // 內(nèi)層循環(huán)對(duì) 每一組 進(jìn)行直接排序操作
            // i = 2 ；j = 0, j-=2 = 0 - 2 = -2，arr[j] = 3 ，跳出循環(huán)，
            //      這是對(duì)第 1 組中的 3,1 進(jìn)行比較，1 為無序列表中的比較元素，3 為有序列表中的最后一個(gè)元素，3 > 1，進(jìn)行交換
            //      交換后的數(shù)組：[1, 5, 3, 6, 0, 8, 9, 4, 7, 2]
            //      第 1 組：[1,3,0,9,7]
            
            // i = 3 ；j = 1, j-=2 = 1 - 2 = -1,arr[j] = 5 ，跳出循環(huán)
            //      這是對(duì)第 2 組中的 5,6 進(jìn)行比較，6 為無序列表中的比較元素，5 為有序列表中的最后一個(gè)元素，5 < 6，不進(jìn)行交換
            //      交換后的數(shù)組：[1, 5, 3, 6, 0, 8, 9, 4, 7, 2] , 沒有交換
            //      第 2 組：[5,6,8,4,2]
            
            // i = 4 ；j = 2, j-=2 = 2 - 2 = 0，arr[j] = 3 ，
            //      這是對(duì)第 1 組中的 3,0 進(jìn)行比較，0 為無序列表中的比較元素，3 為有序列表中的最后一個(gè)元素，3 > 0，進(jìn)行交換
            //      交換后的數(shù)組：[1, 5, 0, 6, 3, 8, 9, 4, 7, 2]，
            //           第 1 組：[1,0,3,9,7]
            //      由于 2 - 2 = 0，此時(shí) j = 0，滿足條件，繼續(xù)循環(huán) i = 4 ：j = 0, j-=2 = 0 - 2 = -2，arr[j] = 1 ，跳出循環(huán)
            //      這是對(duì)第 1 組中的有序列表中的剩余數(shù)據(jù)進(jìn)行交換，1,0, 1>0 ，他們進(jìn)行交換（這里也就是完成有序列的一個(gè)排序）
            //           第 1 組：[0,1,3,9,7]
            //雖然有可能本次的排序完成了但是排序循環(huán)還是會(huì)循環(huán)下去，直到循環(huán)結(jié)束，后面的移動(dòng)法會(huì)解決該問題
            //以此類推
            for (int j = i - 2; j >= 0; j -= 2) {
                if (arr[j] > arr[j + 2]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 2];
                    arr[j + 2] = temp;
                }
            }
        }
        System.out.println("第 2 輪排序后：" + Arrays.toString(arr));

        // 第 3 輪：上一輪排序后的數(shù)組：[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
        // 將 10 個(gè)數(shù)字分成了 1 組（上一次的增量 2 / 2），增量也為 1，需要對(duì) 1 組進(jìn)行排序
        for (int i = 1; i < arr.length; i++) {
            // 第 1 組：[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
            // i = 1 ：j = 0, j-=1 = 0 - 1 = -1，arr[j] = 0 ，跳出循環(huán)
            //      0 為有序列表中的最后一個(gè)元素，2 為無須列表中要比較的元素。 0 < 2,不交換
            //      [0, 2    有序 <-> 無序, 1, 4, 3, 5, 7, 6, 9, 8]
            // i = 2 ：j = 1, j-=1 = 1 - 1 = o，arr[j] = 2 ，
            //      2 為有序列表中的最后一個(gè)元素，1 為無序列表中要比較的元素， 2 > 1,交換
            //      交換后：[0, 1, 2,     4, 3, 5, 7, 6, 9, 8]
            //      由于不退出循環(huán)，還要比較有序列表中的數(shù)據(jù)，0 與 1 ，0 < 1 ，不交換，退出循環(huán)
            //后面的以此類推，就是一個(gè)插入排序
            for (int j = i - 1; j >= 0; j -= 1) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        System.out.println("第 3 輪排序后：" + Arrays.toString(arr));
    }

    @Test
    public void shellSortTest() {
        int arr[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        System.out.println("原始數(shù)組：" + Arrays.toString(arr));
        shellSort(arr);
    }

    /**
     * 根據(jù)前面的分析，得到規(guī)律，變化的只是增量步長，那么可以改寫為如下方式
     */
    public void shellSort(int[] arr) {
        int temp = 0;
        // 第 1 層循環(huán)：得到每一次的增量步長
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            // 第 2 層和第 3 層循環(huán)，是對(duì)每一個(gè)增量中的每一組進(jìn)行插入排序
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
            System.out.println("增量為 " + gap + " 的這一輪排序后：" + Arrays.toString(arr));
        }
    }

  /**
     * 大量數(shù)據(jù)排序時(shí)間測試
     */
    @Test
    public void bulkDataSort() {
        int max = 80_000;
//        int max = 8;
        int[] arr = new int[max];
        for (int i = 0; i < max; i++) {
            arr[i] = (int) (Math.random() * 80_000);
        }

        Instant startTime = Instant.now();
        shellSort(arr);
//        System.out.println(Arrays.toString(arr));
        Instant endTime = Instant.now();
        System.out.println("共耗時(shí)：" + Duration.between(startTime, endTime).toMillis() + " 毫秒");
    }

 /**
     * 移動(dòng)法希爾排序
     */
    @Test
    public void moveShellSortTest() {
        int arr[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        System.out.println("原始數(shù)組：" + Arrays.toString(arr));
        moveShellSort(arr);
    }

    /**
     * 插入排序采用移動(dòng)法
     */
    public void moveShellSort(int[] arr) {
        // 第 1 層循環(huán)：得到每一次的增量步長
        // 增量并逐步縮小增量
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            /**
             這里的內(nèi)層循環(huán)，除了是獲得每一組的值（按增量取），
             移動(dòng)法使用的是簡單插入排序的算法 {@link InsertionSortTest#processSelectSort2(int[])}
             唯一不同的是，這里的組前一個(gè)是按增量來計(jì)算的
             */
            // 每一輪，都是針對(duì)某一個(gè)組的插入排序中：待排序的起點(diǎn)
            for (int i = gap; i < arr.length; i++) {
                int currentInsertValue = arr[i]; // 無序列表中的第一個(gè)元素
                int insertIndex = i - gap; // 有序列表中的最后一個(gè)元素
                while (insertIndex >= 0
                        && currentInsertValue < arr[insertIndex]) {
                    // 比較的數(shù)比前一個(gè)數(shù)小，則前一個(gè)往后移動(dòng)
                    arr[insertIndex + gap] = arr[insertIndex];
                    insertIndex -= gap;
                }
                // 對(duì)找到的位置插入值
                arr[insertIndex + gap] = currentInsertValue;
            }
            System.out.println("增量為 " + gap + " 的這一輪排序后：" + Arrays.toString(arr));
        }
    }

    /**
     * 移動(dòng)法，大數(shù)據(jù)量測試速度
     */
    @Test
    public void moveBulkDataSort() {
        int max = 80_000;
//        int max = 8;
        int[] arr = new int[max];
        for (int i = 0; i < max; i++) {
            arr[i] = (int) (Math.random() * 80_000);
        }

        Instant startTime = Instant.now();
        moveShellSort(arr);
//        System.out.println(Arrays.toString(arr));
        Instant endTime = Instant.now();
        System.out.println("共耗時(shí)：" + Duration.between(startTime, endTime).toMillis() + " 毫秒");
    }