【数据结构与算法之排序与查找】希尔排序

矫情吗；* 2024-03-25 16:38 103阅读 0赞

#### 【数据结构与算法之排序与查找】希尔排序 ####

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

*   *   *  【数据结构与算法之排序与查找】希尔排序

希尔排序也称为缩小增量排序，它是对直接插入排序算法的一种改进，因此希尔排序的效率比直接插入排序、冒泡排序、简单选择排序都高。

【基本思想】将整个待排序序列划分为若干子序列，分别对子序列进行排序，然后逐步缩小子序列的间隔，并重复，直到划分间隔变为1。

具体来说，可以设置一个元素间隔增量，然后依据这个间隔对序列进行分割，从第1个元素开始依次分为若干子序列。

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

这样序列 \{5, 30, 7, 9, 20, 10\} 就被划分为了3个子序列，对这3个子序列分别进行排序，可以直接使用直接插入排序、冒泡等算法，然后缩小间隔，依据新的间隔值再对序列进行划分 ，再对子序列进行排序，直到间隔缩小为1。

举个栗子：

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

排序算法的时间主要花费在排序过程中移动元素的过程上，在希尔排序中，因为最初间隔取值较大，所以排序时元素的移动跨度较大，这在一定程序上减少了序列中元素的频繁移动，当间隔缩小到1 时，序列就已经基本有序了，所以不需要移动较多元素。

Java 实现希尔：

public static void shellSort(int[] array) {
        
    
        int gap = array.length;
        int flag = 0;
    
        while (gap > 1) {
        
            gap = gap / 2; // 按照经验每次将间隔缩小一半
            do {
        
    
                flag = 0;
                for (int i = 0; i < array.length - gap; i++) {
        
                    int j = i + gap;
                    // 子序列用冒泡处理
                    if (array[i] > array[j]) {
        
                        // 交换
                        int tmp = array[i];
                        array[i] = array[j];
                        array[j] = tmp;
                        flag = 1;
                    }
                }
            } while (flag != 0);
        }
    }

测试

public static void main(String[] args) {
        
    
        int[] array = {
        3, 12, 20, 1, 0, 5, 8, 19, 5};
        shellSort(array);
    
        for (int e : array) {
        
            System.out.print(e + " ");
        }
    
    }

运行结果

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

[8cfc8848121b462294f42c0bdaf54c35.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/74a28dc675424b90a401642b8b53ace6.png
[8f5d355050184d218d9134107320d0f9.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/4061151d505d4b86964aefca81d40cf0.png
[ecdcd551517043748dc322e8b859a124.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/8fa9e0731c3b4120865527197595c0fd.png