Carson带你学数据结构：希尔排序，复杂度最高的排序算法

矫情吗；* 2022-09-17 03:09 149阅读 0赞

![e42c52b9af8d79486a0f3cd0e50df7b7.png][]

--------------------

# 目录 #

![示意图][bab6c0bbf642652f3101805e0025552a.png]

--------------------

# 1. 简介 #

*  **也称：缩小增量 排序**，属于 内排序算法中 的 **插入排序类别**
 *  是对 **直接插入排序算法** 的优化和升级

--------------------

# 2. 算法原理 #

![示意图][b93c39ccc123d3270a099ec33acb024c.png]

--------------------

# 3. 算法示意图 #

步骤1：初始状态  
![c4cc1167a056101bee4441c5c4591d03.png][]

步骤2：跳跃分割 & 排序  
![23d3b3af0a422258783b631de3c913c9.png][]

--------------------

# 4. 算法实现 #

public class ShellSort {
        /**
         * 希尔排序
         */
        public static void shellSort(int[] srcArray) {
    
            int j = 0;
            int temp = 0;
    
            // 增量序列值 计算公式 = 前1个增量序列值 / 2，直到增量序列值 = 1为止
            // 第1个值 = 初始值 = 序列长度 / 2
            for (int increment = srcArray.length / 2; increment > 0; increment /= 2) {
    
                // 根据增量值选取子序列
                for (int i = increment; i < srcArray.length; i++) {
    
                    temp = srcArray[i];
    
                    // 对子序列执行直接插入排序，即 循环两两比较子序列的值
                    for (j = i - increment; j >= 0; j -= increment) {
    
                        if (temp < srcArray[j]) {
    
                            // 将小的元素放到前面、大的元素放到后面
                            srcArray[j + increment] = srcArray[j];
                        } else {
                            break;
                        }
                    }
                    srcArray[j + increment] = temp;
                }
    
    
                // 输出 根据增量值排序后的序列
                System.out.println("增量值为:" + increment + "，排序结果如下：");
                for (int a = 0; a < srcArray.length; a++) {
                    System.out.println(srcArray[a]);
                }
            }
        }
    
        /**
         * 执行 希尔排序
         */
        public static void main(String[] args) {
    
            // 定义待排序数列
            int[] src = new int[]{ 4, 3, 6, 2, 7, 1, 5, 8 };
    
            // 输出结果
            shellSort(src);
    
        }
    
    }

测试结果

增量值为:4，排序结果如下：
    4
    1
    5
    2
    7
    3
    6
    8
    增量值为:2，排序结果如下：
    4
    1
    5
    2
    6
    3
    7
    8
    增量值为:1，排序结果如下：
    1
    2
    3
    4
    5
    6
    7
    8

`Demo`地址：[Carson\_Ho的Github地址：希尔排序][Carson_Ho_Github]

--------------------

# 5. 性能分析 #

以下将分析算法的性能：时间复杂度、空间复杂度、稳定性  
![示意图][1b89761925bb908bdb7204a0ebc4a255.png]

--------------------

Carson带你学数据结构系列文章：  
[Carson带你学数据：线性表-数组、链表][Carson_-]  
[Carson带你学数据：特殊的线性表-栈、队列][Carson_- 1]  
[Carson带你学数据：串][Carson]  
[Carson带你学数据：树][Carson 1]  
[Carson带你学数据：二叉树][Carson 2]  
[Carson带你学数据：图][Carson 3]  
[Carson带你学数据：查找][Carson 4]

--------------------

# 欢迎关注Carson\_Ho的[CSDN博客][CSDN] ！ #

博客链接：https://carsonho.blog.csdn.net/  
![e42c52b9af8d79486a0f3cd0e50df7b7.png][]

--------------------

# 请点赞！因为你的鼓励是我写作的最大动力！ #

[e42c52b9af8d79486a0f3cd0e50df7b7.png]: /images/20220828/b3fb9e2888b9409abea6aaaf171582d8.png
[bab6c0bbf642652f3101805e0025552a.png]: /images/20220828/3a99247a8bc4492b9d0b947d31690654.png
[b93c39ccc123d3270a099ec33acb024c.png]: /images/20220828/8df1c49f336f4f2da4e4ed2c03e7ea45.png
[c4cc1167a056101bee4441c5c4591d03.png]: /images/20220828/3ba947b98140419aaef3cf1d6fd1e879.png
[23d3b3af0a422258783b631de3c913c9.png]: /images/20220828/201fe8130420413fa6abd5e024befed7.png
[Carson_Ho_Github]: https://github.com/Carson-Ho/AlgorithmLearning
[1b89761925bb908bdb7204a0ebc4a255.png]: /images/20220828/236040bda49d440abf0c077e1795dffe.png
[Carson_-]: https://carsonho.blog.csdn.net/article/details/87910747
[Carson_- 1]: https://carsonho.blog.csdn.net/article/details/103452029
[Carson]: https://carsonho.blog.csdn.net/article/details/103556469
[Carson 1]: https://carsonho.blog.csdn.net/article/details/120695951
[Carson 2]: https://carsonho.blog.csdn.net/article/details/103676620
[Carson 3]: https://carsonho.blog.csdn.net/article/details/108571561
[Carson 4]: https://carsonho.blog.csdn.net/article/details/108723161
[CSDN]: https://carsonho.blog.csdn.net/