希尔排序

希尔排序

希尔排序是一种递减增量排序算法，是时间第一个突破$O(n^2)$的排序算法，核心思想在于增量缩减
例如将6 5 4 3 2 1排序得到升序结果
第一轮
计算增量 gap = arr.length/2 = 6/2 = 3
按照 0+n*gap 的格式找到最后一个小于数据长度的元素
所以索引（0，0+3）（1，1+3）（2，2+3）比较，交换6和3位置，交换5和2位置，交换 4和1位置
得到 3 2 1 6 5 4

第二轮
计算增量 （3+1）/2 向上取整
（0，0+2，0+2+2） （1，1+2，1+2+2） 比较，交换3和1位置，交换4和6位置
得到 1 2 3 4 5 6 完成排序

点此链接，可以查看在线效果图

Java代码

package sort.insert;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/**
 * @author ShaoYJ
 * @date 2022/10/17 周一
 * @desc 得到升序结果
 */
public class ShellSort {
    public static void main(String[] args) {
//        Integer[] arr = scanNum();
        Integer[] arr = {6,54,32,21,9,100};
//        Integer[] arr = {5,4,3,2,1};


        System.out.println("排序前:" + Arrays.toString(arr));
        sort(arr);
        System.out.print("排序后:" + Arrays.toString(arr));
    }

    private static void sort(Integer[] arr) {
        int len = arr.length;
        int gap = (len + 1) / 2;
        boolean flag = true;
        while (gap >=1) {
//            i 表示第一个gap前的数字
            for (int i = 0; i < gap; i++) {
//               循环每次的增量都是当前的gap数值
                for (int j = i + gap; j < len; j += gap) {
//                       本组内部  从后往前采用 插入排序，实现数据的升序排列
                    for (int k = j - gap; k >= i; k -= gap) {
                        if (arr[j] < arr[k]) {
//                          当前点的值小于前面点的值 向后移
                            int tmp = arr[j];
                            arr[j] = arr[k];
                            arr[k] = tmp;
                        }
                    }
                }
            }
            //   此处gap+1 是为了保证当gap为奇数的时候，实现向上取整
            gap = (gap+1) / 2;
//          此处由于设计的是 gap = (gap+1)/2 所以 gap会在等于1的时候不能正确退出，因此设置一个标志量，用于限制gap=1只能在while中走一次
            if(!flag){
                break;
            }

            if(gap==1){
                flag = false;
            }
        }
//        增量从length/2开始，然后增量依次缩小为一半


    }

    public static Integer[] scanNum() {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<>();
        System.out.print("输入一串数字，空格分开，以#结束:");
        while (!sc.hasNext("#")) {
            int a = sc.nextInt();
            list.add(a);
        }
//       list 转 Integer : 提供首地址即可
        return list.toArray(new Integer[0]);
    }


}

运行结果：