希尔排序【Java算法】

阳光穿透心脏的1/2处 2023-10-14 20:24 52阅读 0赞

#### 文章目录 ####

*   *  1. 概念
     *  2. 思路
     *  3. 代码实现

### 1. 概念 ###

> 希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。

推荐一个B站六分钟的视频，PPT动画做的非常好，清晰明了。

![在这里插入图片描述][d28448dd1e954cf9ac235f09f302480d.png_pic_center]

### 2. 思路 ###

① 希尔排序采用跳跃式的分组方式，什么是跳跃式？也就是说同一组内的成员在原序列中实际上是互相隔着一段距离的，它们被迫抽出来组成一队，内部采用插入排序比较大小。它们互相隔着的距离是相等的，这个距离我们称它为增量，增量怎么确定？一般来说，初始增量值为序列长度的一半，接下来我们根据增量值计算分组，如下图增量为5，所以索引0跟索引5一组，索引1跟索引6一组 …，以此类推，序列被分成了五组；

![在这里插入图片描述][b012013a28c84bdda727abaaa980b383.png_pic_center]  
② 分了组之后，组员内部要进行插入排序的，但是这里的插入排序步长其实并不是1，我们知道原本的插入排序是从右往左一步一步地比较大小并插入的，但是希尔排序是跳跃式分组的，虽然说你们被分到了同一个队伍里，但是不要忘记了，你们本身的索引并不相连，索引还是原来位置的索引，所以，在这里插入排序的时候，每一步的长度应该是增量的大小，除了步长不一样外，其它思路都不变；

③ 在第一轮排序完成之后，发现整体上序列的顺序有了一个大体的趋势，小的基本在左边，大的基本在右边，但这才是第一步还不算排好序；

④ 再开始下一轮排序，每一轮开始时的增量值都应是上一轮增量值的一半。原理还不变，外部分组，内部插入排序，什么时候不再分组，不再排序？增量值一直减半，总有一天它会减为1，到1的时候就是全体序列进行最基本的插入排序了，没错这是最后一步，所以终止条件就是增量值开始小于1，这时候的序列已经完全有序。

### 3. 代码实现 ###

import java.util.Arrays;
    
    public class Test {
        
        public static void main(String[] args) {
        
            int[] arr = {
        2, 9, 3, 11, 7, 8, 4, 1, 6};
            int[] newArr = sort(arr);
            System.out.println(Arrays.toString(newArr));
        }
        public static int[] sort(int[] arr) {
        
            //控制增量值，初始值为序列长度的一半，每次减半，步长为0时停止
            for (int step = arr.length / 2; step > 0; step /= 2) {
        
                //控制待插入元素的位置，初始值为增量值
                for (int i = step; i < arr.length; i++) {
        
                    //待插入元素
                    int insertVal = arr[i];
                    //待比较元素初始位置
                    int index = i - step;
                    //控制待比较元素的位置，初始值为待插入元素的位置减去增量值，即index
                    while (index >= 0 && insertVal < arr[index]) {
        
                        //当前待比较元素向后移一位，这里的一位就是step长度
                        arr[index + step] = arr[index];
                        //指针向左挪动一位，继续跟下一个元素作比较
                        index -= step;
                    }
                    //退出循环后后，将待插入元素插入到index的下一位
                    arr[index + step] = insertVal;
                }
            }
            return arr;
        }
    }

![在这里插入图片描述][69f66961fdf74854beb613adb7b79dff.png]

[d28448dd1e954cf9ac235f09f302480d.png_pic_center]: https://img-blog.csdnimg.cn/d28448dd1e954cf9ac235f09f302480d.png#pic_center
[b012013a28c84bdda727abaaa980b383.png_pic_center]: https://img-blog.csdnimg.cn/b012013a28c84bdda727abaaa980b383.png#pic_center
[69f66961fdf74854beb613adb7b79dff.png]: https://img-blog.csdnimg.cn/69f66961fdf74854beb613adb7b79dff.png