​
​

活动地址：CSDN21天学习挑战赛

怕什么真理无穷，进一步有一份的欢喜。

【21天学习挑战赛】希尔排序

✌我为什么参与挑战赛

1，机缘

读到研一了，暑假假期打开私信发现这个挑战赛就鼓起勇气参加了。

2，期待的收获

A, 本人在华南理工大学攻读专硕，目前研究方向是图像恢复，从事深度学习相关工作，目标是从事Java后端开发。
B, 期待您的反馈，如果有什么不对的地方，欢迎指正！
C, 期待认识志同道合的领域同行或技术交流。
如果感觉博主的文章还不错的话，还请👍关注、点赞、收藏三连支持👍一下博主哦

🍉希尔排序的图解

希尔排序是对直接插入排序(参考资料)改进后的算法，提高效率。核心思想是分组来减少减少待排序的个数，通过将相距某个增量的记录组成一个子序列，这样保证子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序的。

基本有序：将小的关键字基本放在前面，大的基本放在后面，不大不小放在中间。

假设我们有这样一个数组，arr={7, 6, 9, 3, 1, 5, 2, 4}，
用颜色表示分组，可以直观发现增量等于分组数

1. 第一趟：
   
2. 第二趟：
   
3. 第三趟
   

💬希尔排序的定义

希尔排序也称缩小增量排序，是直接插入排序的一种改进算法，更为高效。希尔排序的核心思想是先将数据进行分组，在每个分组中进行直接插入排序。通过不断的更改增量，得到新的分组，在每个组中再进行直接插入排序，直到增量减少至1，最后一次对所有的集合元素进行一次直接插入排序.

✨希尔排序的优劣

优势

对于希尔排序来说，时间复杂度达到了O(n4/3)，算法在执行过程中只需要定义的几个临时变量，空间复杂度为常数级：O(1)。

劣势

实现复杂，并不是最快速的排序算法，比较适合中等数量的数据

🍵希尔排序的步骤

1. 确定增量
2. 在每个分组中要直接插入排序
3. 循环1,2步，直到增量=0

✍️ 算法实现

class ShellSort {

    public static void main(String[] args) {
        // input data
        int[] a = {7, 6, 9, 3, 1, 5, 2, 4};
        sort(a);
        // 查看排序结果
        System.out.println(Arrays.toString(a));
    }

    public static void sort(int[] arr) {
        int j;
        int increment = arr.length >> 1;//增量
        while (increment > 0) {
            for (int i = increment; i < arr.length; i++) {
                int tmp = arr[i];
                //插入排序
                for (j = i; j >= increment && tmp < arr[j - increment]; j -= increment) {
                    arr[j] = arr[j - increment];
                }
                arr[j] = tmp;
            }
            increment = increment >> 1;// 增量每次除以2
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
⭐️ 收藏，你的青睐是我努力的方向！
✏️ 评论，你的意见是我进步的财富！