算法导论之经典算法：希尔排序全面解析

2021-04-16 09:16 261人阅读评论(0)

写在前面：博主是一只经过实战开发历练后投身培训事业的“小山猪”，昵称取自动画片《狮子王》中的“彭彭”，总是以乐观、积极的心态对待周边的事物。本人的技术路线从Java全栈工程师一路奔向大数据开发、数据挖掘领域，如今终有小成，愿将昔日所获与大家交流一二，希望对学习路上的你有所助益。同时，博主也想通过此次尝试打造一个完善的技术图书馆，任何与文章技术点有关的异常、错误、注意事项均会在末尾列出，欢迎大家通过各种方式提供素材。

对于文章中出现的任何错误请大家批评指出，一定及时修改。
有任何想要讨论和学习的问题可联系我：zhuyc@vip.163.com。
发布文章的风格因专栏而异，均自成体系，不足之处请大家指正。

算法导论之经典算法：希尔排序全面解析

本文关键字：算法导论、经典算法、插入排序、希尔排序、算法实践

文章目录

算法导论之经典算法：希尔排序全面解析

一、什么是算法

本专栏为《手撕算法》栏目的子专栏：《算法导论》，会讲述一些经典算法，并进行分析。在此之前我们要先了解什么是算法，能够解决什么样的问题。

1. 算法的定义

以下为经典教材《Introduction.to.Algorithms》开篇中的内容。

Informally, an algorithm is any well-deﬁned computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.

可以看到，任何被明确定义的计算过程都可以称作算法，它将某个值或一组值作为输入，并产生某个值或一组值作为输出。所以算法可以被称作将输入转为输出的一系列的计算步骤。
这样的概括是比较标准和抽象的，其实说白了就是步骤明确的解决问题的方法。由于是在计算机中执行，所以通常先用伪代码来表示，清晰的表达出思路和步骤，这样在真正执行的时候，就可以使用不同的语言来实现出相同的效果。
概括的说，算法就是解决问题的工具。在描述一个算法时，我们关注的是输入与输出。也就是说只要把原始数据和结果数据描述清楚了，那么算法所做的事情也就清楚了。我们在设计一个算法时也是需要先明确我们有什么和我们要什么，这一点相信大家在后面的文章中会慢慢体会到。

2. 补充的概念

数据结构

算法经常会和数据结构一起出现，这是因为对于同一个问题（如：排序），使用不同的数据结构来存储数据，对应的算法可能千差万别。所以在整个学习过程中，也会涉及到各种数据结构的使用。
常见的数据结构包括：数组、堆、栈、队列、链表、树等等。

算法的效率

在一个算法设计完成后，还需要对算法的执行情况做一个评估。一个好的算法，可以大幅度的节省运行的资源消耗和时间。在进行评估时不需要太具体，毕竟数据量是不确定的，通常是以数据量为基准来确定一个量级，通常会使用到时间复杂度和空间复杂度这两个概念。

时间复杂度

通常把算法中的基本操作重复执行的频度称为算法的时间复杂度。算法中的基本操作一般是指算法中最深层循环内的语句（赋值、判断、四则运算等基础操作）。我们可以把时间频度记为T(n)，它与算法中语句的执行次数成正比。其中的n被称为问题的规模，大多数情况下为输入的数据量。
对于每一段代码，都可以转化为常数或与n相关的函数表达式，记做f(n)。如果我们把每一段代码的花费的时间加起来就能够得到一个刻画时间复杂度的表达式，在合并后保留量级最大的部分即可确定时间复杂度，记做O(f(n))，其中的O就是代表数量级。
常见的时间复杂度有（由低到高）：O(1)、O( $log _{2} n$ )、O(n)、O( $n\log _{2} n$ )、O( $n^{2}$ )、O( $n^{3}$ )、O( $2^{n}$ )、O(n!)。

空间复杂度

程序从开始执行到结束所需要的内存容量，也就是整个过程中最大需要占用多少的空间。为了评估算法本身，输入数据所占用的空间不会考虑，通常更关注算法运行时需要额外定义多少临时变量或多少存储结构。如：如果需要借助一个临时变量来进行两个元素的交换，则空间复杂度为O(1)。

伪代码约定

伪代码是用来描述算法执行的步骤，不会具体到某一种语言，为了表达清晰和标准化，会有一些约定的含义：
缩进：表示块结构，如循环结构或选择结构，使用缩进来表示这一部分都在该结构中。
循环计数器：对于循环结构，在循环终止时，计数器的值应该为第一个超出界限的值。
to：表示循环计数器的值增加。
downto：表示循环计数器的值减少。
by：循环计数器的值默认变化量为1，当大于1时可以使用by。
变量默认是局部定义的。
数组元素访问：通过"数组名[下标]"形式，在伪代码中，下标从1开始（"A[1]“代表数组A的第一个元素）。
子数组：使用”…"来代表数组中的一个范围，如"A[i…j]"代表从第i个到第j个元素组成的子数组。
对象与属性：复合的数据会被组织成对象，如链表包含后继（next）和存储的数据（data）,使用“对象名 + 点 + 属性名”。
特殊值NIL：表示指针不指向任何对象，如二叉树节点无子孩子可认为左右子节点信息为NIL。
return：返回到调用过程的调用点，在伪代码中允许返回多个值。
and和or：与运算和或运算默认短路，即如果已经能够确定表达式结果时，其他条件不会去判断或执行。

二、插入排序

1. 插入排序介绍

插入排序的基本思路是每次插入一个元素，每一趟完成对一个待排元素的放置，直到全部插入完成。

直接插入排序

直接插入排序是一种最简单的排序方法，过程就是将每个待排元素逐个插入到已经排好的有序序列中。
文章传送门：算法导论之经典算法：直接插入排序全面解析。

折半插入排序

由于在插入排序的过程中，已经生成了一个（排好的元素组成的）有序数列。所以在插入待排元素时可以使用折半查找的方式更快速的确定新元素的位置，当元素个数较多时，折半插入排序优于直接插入排序。
文章传送门：算法导论之经典算法：折半插入排序全面解析。

希尔排序

希尔排序可以看做是分组插入的排序方法，把全部元素分成几组（等距元素分到一组），在每一组内进行直接插入排序。然后继续减少间距，形成新的分组，进行排序，直到间距为1时停止。

2. 希尔排序

输入

n个数的序列，通常直接存放在数组中，可能是任何顺序。

输出

输入序列的一个新排列，满足从小到大的顺序（默认讨论升序，简单的修改就可以实现降序排列）。

算法说明

希尔排序也称缩小增量排序，是直接插入排序的一种改进算法，更为高效。希尔排序的核心思想是先将数据进行分组，在每个分组中进行直接插入排序。通过不断的更改增量，得到新的分组，在每个组中再进行直接插入排序，直到增量减少至1，最后一次对所有的集合元素进行一次直接插入排序。
由于在前几次的分组和排序中，已经调整了元素的位置，所以最后一次的元素串位次数会大大减少。在分组的过程中，增量d不断变化，通常第一个增量的选取不会超过n/2（这样每组中至少有两个元素），然后每次减半，直到增量为1。如果这样调节增量，则分组排序可以在不超过** $log _{2} n$ **的情况下，完成操作。

算法流程

以下图片来源于网络：

输入数据共计10个元素：5，2，3，4，9，7，1，8，0，6。
分组后在组内进行直接插入排序，依然在原数据结构上进行，串位时以d为间隔进行操作。
第一次分组：取d=5，数据被分为5组，每组2个元素。
第二次分组：取d=2，数据被分为2组，每组5个元素。
第三次分组：取d=1，数据被分为1组，组内10个元素。

与直接插入排序不同的是，每次分组排序后，整体序列更加接近有序，但是不产生有序区。可以看到，在分组中的每次排序，都是把较小的数尽量的往左侧丢，因为组内的数据量较小，这样就能有效的减少数据串位的次数，在最后一次的调整时就可以减少数据的串位次数和串位距离。

3. 伪代码

希尔排序中也用到了直接插入排序算法，伪代码如下：

d = A.length / 2
while d > 0
    for i = 1 to d
        for j = i + d to A.length by d
            tmp = A[j]
            k = j - d
            while k > 0 and A[k] > tmp
                A[k + d] = A[k]
                k = k - d
            A[k + d] = tmp
    d = d / 2

十分重要：本代码中固定了d的变化规律为每次取一半，实际上并不是固定的，对于不同的数据集使用不同的增量序列会收获不同的效果，增量序列也会直接影响到算法的执行效率。

最外层的while循环控制一共执行几趟排序，取决于d的变化
第一层for循环用于控制在每个分组中要执行的操作
第二层for循环就是我们之前熟悉的直接插入排序代码

三、算法实践

1. 算法实现

输入数据（input）：11，34，20，10，12，35，41，32，43，14
Java源代码

public class ShellSort {
   

    public static void main(String[] args) {
   
        // input data
        int[] a = {
   11,34,20,10,12,35,41,32,43,14};
        // 初始化增量
        int d = a.length / 2;
        // 控制每一次的分组排序
        while (d > 0){
   
            // 控制每一组内的直接插入排序
            for (int i = 0;i < d;i++){
   
                // 组内进行直接插入排序
                for (int j = i + d;j < a.length;j+=d){
   
                    int tmp = a[j];
                    int k = j - d;
                    while(k > 0 && a[k] > tmp){
   
                        a[k + d] = a[k];
                        k = k -d;
                    }
                    a[k + d] = tmp;
                }
            }
            // 增量按一定规律每次变化
            d = d / 2;
        }
        // 查看排序结果
        for (int data : a){
   
            System.out.print(data + "\t");
        }
    }

}

执行效果

2. 时间复杂度

在上文中已经提到，增量的变化会直接影响到希尔排序的性能，因此希尔排序的时间复杂度与增量序列高度相关，以下列举几个经典增量序列：

Shell增量序列

递推公式： $h_{t}=\left\lfloor\frac{n}{2}\right\rfloor, h_{k}=\left\lfloor\frac{h_{k+1}}{2}\right\rfloor$
最坏时间复杂度：O( $n^{2}$ )

Hibbard增量序列

递推公式： $h_{1}=1, h_{i}=2 * h_{i-1}+1$
最坏时间复杂度： $\Theta\left(n^{3 / 2}\right)$

Sedgewick 增量序列

通项公式： $h_{i}$ = max(9 x $4^i$ - 9 x $2^i$ + 1, $4^i$ - 3 x $2^i$ + 1)
最坏时间复杂度：O( $n^{4 / 3}$ )

时间复杂度总结

综上可知，在使用希尔排序时，可以使最坏时间复杂度优化至O( $n^{4 / 3}$ )。

3. 空间复杂度

算法在执行过程中只需要定义的几个临时变量，所以空间复杂度为常数级：O(1)。

转载：https://blog.csdn.net/u012039040/article/details/115714076

查看评论

小言_互联网的博客

小言_互联网的博客

个人资料

文章分类

文章存档

阅读排行

评论排行

推荐文章