排序算法之希尔排序

向右看齐 2023-02-23 05:21 12阅读 0赞

# 希尔排序 #

1959年由唐纳德·希尔（Donald Shell）提出希尔排序。

希尔排序的思想：把数组中的元素看作是一个矩阵，分成m列，逐列进行排序（一般采用插入排序），m从某个整数逐渐减为1，当m为1时，整个序列将完全有序。因此，希尔排序也被称为递减增量排序（Diminishing Increment Sort）。

矩阵的列数取决于步长序列（step sequence），比如，如果步长序列为\{1,5,19,41,109,…\}，就代表依次分成109列、41列、19列、5列、1列进行排序。不同的步长序列，执行效率也不同。

## 实例 ##

希尔本人给出的步长序列是n/2^k（其中n为数组长度），例如要对下面的数组进行排序，n为16，步长序列是\{1, 2, 4, 8\}：

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

首先分成8列进行排序：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70]

然后再分成4列进行排序：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 1]

再分成2列进行排序：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 2]

最后分成一列进行排序：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 3]  
最后数组中的元素就变成有序的了。

疑惑：直接分成一列进行排序不就行了，为什么要分成这么多列？不难看出来，从8列变为1列的过程中，逆序对的数量在逐渐减少，而希尔排序底层会使用插入排序，插入排序的时间复杂度与逆序对的数量成正比，这样就可以提高插入排序的效率。

因此希尔排序底层一般使用插入排序对每一列进行排序，也很多资料认为希尔排序是插入排序的改进版。

## 动图演示 ##

![在这里插入图片描述][20200705212524499.gif]

## 代码实现 ##

protected void sort() { 
    
            List<Integer> stepSequence = shellStepSequence();
            
            for (Integer step : stepSequence) { 
                sort(step);
            }
    
        }
    
        private void sort(Integer step) { 
    
            // 对每一列进行插入排序
            for (int col = 0; col < step; col++) { 
    
                // 插入排序
                for (int begin = col + step; begin < array.length; begin += step) { 
                    int cur = begin;
                    E v = array[cur];
                    while (cur > col && cmp(v, array[cur - step]) < 0) { 
                        array[cur] = array[cur - step];
                        cur -= step;
                    }
                    array[cur] = v;
                }
            }
        }
    
        private List<Integer> shellStepSequence() { 
    
            // n/2^k
            int n = array.length;
            List<Integer> list = new ArrayList<>();
    
            while ((n >>= 1) > 0) { 
                list.add(n);
            }
    
            return list;
        }

## 复杂度与稳定性 ##

最好情况是步长序列只有1，且序列几乎有序，时间复杂度为O(n)。

希尔本人给出的步长序列，最坏情况时间复杂度是 O(n^2)。

希尔排序的时间复杂度与步长序列有关。

更多精彩内容关注本人公众号：架构师升级之路  
![在这里插入图片描述][20200627175030665.jpg]

[20200705185156970.png]: https://img-blog.csdnimg.cn/20200705185156970.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200705185205337.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200705185212873.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/202007051852287.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200705185238459.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk=,size_16,color_FFFFFF,t_70
[20200705212524499.gif]: https://img-blog.csdnimg.cn/20200705212524499.gif
[20200627175030665.jpg]: https://img-blog.csdnimg.cn/20200627175030665.jpg