排序算法之希尔排序

￡神魔★判官ぃ 2023-07-12 11:47 0阅读 0赞

**希尔排序介绍**

希尔排序，也称递减增量排序算法（缩小增量排序），是插入排序的一种更高效的改进版本，但希尔排序是非稳定排序算法

**希尔排序基本思想**

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序，随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件被分成一组，算法便终止

**希尔排序算法讲解（需要有直接插入排序算法作为基础知识）**

（说明：分组个数等于下标增量等于步长，说的都是同一个意思，分组=下标增量=步长）

以数组 \{82 ,31 ,29 ,71, 72, 42, 64, 5, 110\} 为例

![20200308154431603.png][]

该数组长度为9，初始增量初始默认设置为数组长度的一半，取整，为4

就可以把以上数组分为以下四个子数组，然后对每个子数组分别进行直接插入排序

子数组1

![20200308154511710.png][]

子数组2

![20200308154731722.png][]

子数组3

![20200308155029345.png][]

子数组4

![2020030815505850.png][]

对每个子数组进行直接插入排序后得到以下数组：

![20200308155206905.png][]

重新设置增量 = 之前增量的1/2 即是4/2=2

在增量为2的前提下，分成以下两个子数组，分别对各个子数组进行直接插入排序

子数组1

![20200308155321643.png][]

子数组2

![2020030815534676.png][]

对每个子数组进行直接插入排序后得到以下数组：

![20200308155427314.png][]

重新设置增量 = 之前增量的1/2 即是2/2=1

增量为1的时候，就是对整个数组分成一组，进行直接插入排序

得到最终排序结果：

![20200308155540503.png][]

**代码实现**

package com.zzb.sort;
    
    import java.util.Arrays;
    
    /**
     * @Auther: Administrator
     * @Date: 2020/3/8 14:36
     * @Description: 希尔排序（直接插入排序的升级版）
     */
    public class ShellSort {
        public static void main(String[] args) {
            int[] array = {82, 31, 29, 71, 72, 42, 64, 5, 110};
    
            shellSort(array);
            System.out.println(Arrays.toString(array));
            /*[5, 29, 31, 42, 64, 71, 72, 82, 110]*/
        }
    
        /**
         * 希尔排序算法
         * @param array 待排序数组
         *
         * 说明：分组个数即为步长，或者即为下表增量
         */
        private static void shellSort(int[] array) {
            //待插入元素
            int insertValue;
            // 初始默认值为各个分组每次循环比较开始时，待插入元素左边的已排序元素的索引位置
            int insertIndex;
            // 对待排序数组进行分组
            // 初始分组个数为数组长度的一半
            // gap /= 2 分组逐步减半，向1靠近
            for(int gap = array.length / 2; gap > 0; gap /= 2) {
                // 对各个分组中的若干元素进行直接插入排序
                // 共有gap个分组
                for(int i = 0; i < gap; i++) {
                    // 取出各个分组中的元素进行直接插入排序
                    // j = gap + i 默认每一个分组中的第一个元素为已排序，需要找出下一个元素与已排序元素进行比较排序
                    // j < array.length 能够获取到每一个分组中的全部元素
                    // j += gap 元素下标差等于步长gap的元素都在同一个分组中
                    for(int j = gap + i; j < array.length; j += gap) {
                        // 如果待插入元素比已排序元素小，则需要比较找出插入位置
                        if(array[j] < array[j - gap]) {
                            //待插入元素
                            insertValue = array[j];
                            // 初始默认值为各个分组每次循环比较开始时，待插入元素左边的已排序元素的索引位置
                            insertIndex = j - gap;
                            // insertIndex >= 0 保证在给待插入元素insertVal找插入位置，数组下标不越界
                            // insertVal < arr[insertIndex] 待插入元素还没有找到要插入的位置
                            while(insertIndex >= 0 && insertValue < array[insertIndex]) {
                                // 如果待插入元素小于已排序元素，则将已排序元素向后移动一个位置
                                array[insertIndex + gap] = array[insertIndex];
                                // 继续与已排序元素进行比较
                                insertIndex -= gap;
                            }
                            // 退出while循环，待插入元素已找到插入位置，为insertIndex + gap
                            array[insertIndex + gap] = insertValue;
                        }
                    }
                }
            }
        }
    }

[20200308154431603.png]: https://img-blog.csdnimg.cn/20200308154431603.png
[20200308154511710.png]: https://img-blog.csdnimg.cn/20200308154511710.png
[20200308154731722.png]: https://img-blog.csdnimg.cn/20200308154731722.png
[20200308155029345.png]: https://img-blog.csdnimg.cn/20200308155029345.png
[2020030815505850.png]: https://img-blog.csdnimg.cn/2020030815505850.png
[20200308155206905.png]: https://img-blog.csdnimg.cn/20200308155206905.png
[20200308155321643.png]: https://img-blog.csdnimg.cn/20200308155321643.png
[2020030815534676.png]: https://img-blog.csdnimg.cn/2020030815534676.png
[20200308155427314.png]: https://img-blog.csdnimg.cn/20200308155427314.png
[20200308155540503.png]: https://img-blog.csdnimg.cn/20200308155540503.png