建议和反馈

请填写你的反馈内容

希尔排序:希尔排序的详细过程图解

2019-09-04 ·12723次阅读 ·读完需要5分钟

在本教程中,您将学习希尔排序的工作原理,即希尔排序的详解过程及图解,此外,您将在C,C ++,Java和Python中找到希尔排序的工作示例。

希尔排序是一种算法,它首先对彼此远离的元素进行排序,并相继减少要排序的元素之间的间隔。它是插入排序的通用版本。

在希尔排序中,对特定时间间隔的元素进行排序。基于所使用的序列,元素之间的间隔逐渐减小。希尔排序的性能取决于给定输入数组使用的序列类型。

使用的一些最佳序列是:

  • 希尔的原始序列:N / 2,N / 4,...,1

  • Knuth的增量:1,4,13,......,(3k - 1)/ 2

  • 塞奇威克的增量:1,8,23,77,281,1073,4193,16577 ...... 4j + 1 + 3·2j + 1。

  • 希巴德的增量:1,3,7,15,31,63,127,255,511 ......

  • Papernov&Stasevich增量:1,3,5,9,17,33,65,......

  • 普拉特:1,2,3,4,6,9,8,12,18,27,16,24,36,54,81 ....


希尔排序如何工作?

    1. 假设,我们需要对以下数组进行排序。
      Shell排序步骤

    2. 我们使用希尔的原始序列(N/2, N/4, ...1作为算法中的间隔。

      在第一个循环中,如果那么数组大小,N = 8那么位于间隔的元素将N/2 = 4被比较并交换,如果它们不是有序的话。Shell Sort步骤
      这个过程继续进行所有剩余的元素。
      Shell排序步骤

      1. 将第0个元素与第4个元素进行比较。

      2. 如果第0个元素大于第4个元素,则第4个元素首先存储在temp变量中,第0个元素(即更大元素)存储在第4个位置,存储的元素存储在temp第0个位置。

    3. 在第二循环中,采用间隔,N/4 = 8/4 = 2并且再次对位于这些间隔的元素进行排序。
      Shell Sort步骤
      你可能会在这一点上感到困惑。Shell Sort步骤
      比较第4和第2位置的元素。还比较了第2和第0位置的元素。比较位于当前间隔的阵列中的所有元素。
       

    4. 其余元素也在进行相同的处理。
      Shell Sort步骤

    5. 最后,当间隔N/8 = 8/8 =1为时,则对以1为间隔的数组元素进行排序。该数组现在已完全排序。
      Shell Sort步骤


      希尔排序算法

      shellSort(array, size)  for interval i <- size/2n down to 1    for each interval "i" in array        sort all the elements at interval "i"end shellSort

      Python,Java和C / C ++示例

      # Python3 program for implementation of Shell Sortdef shellSort(array, n):    gap = n // 2    while gap > 0:        for i in range(gap, n):            temp = array[i]            j = i            while j >= gap and array[j - gap] > temp:                array[j] = array[j - gap]                j -= gap            array[j] = temp        gap //= 2data = [9, 8, 3, 7, 5, 6, 4, 1]size = len(data)shellSort(data, size)print('Sorted Array in Ascending Order:')print(data)

      复杂

      希尔排序是不稳定的排序算法,因为该算法不检查位于间隔之间的元素。

      时间复杂性

      • 最坏情况复杂性:小于或等于O(n2)

        希尔排序的最坏情况复杂度总是小于或等于O(n2)

        据Poonen定理,外壳排序最坏情况的复杂性Θ(NlogN)2/(log logN)2)Θ(NlogN)2/log logN)Θ(N(logN)2)或介于两者之间。
         

      • 最佳案例复杂性O(n*log n)

        当数组已经排序时,每个间隔(或增量)的总比较数等于数组的大小。
         

      • 平均案例复杂性O(n*log n)

        它在附近O(n1.25)


      复杂性取决于所选的间隔。对于所选择的不同增量序列,上述复杂性不同。最佳增量序列未知。

      空间复杂性:

      希尔排序的空间复杂性是O(1)


      希尔排序应用程序

      在以下情况下使用希尔排序:

      • 调用堆栈是开销。uClibc库使用此类型。

      • 递归超出限制。bzip2压缩器使用它。

      • 当close元素相距很远时,插入排序不能很好地执行。希尔排序有助于减少关闭元素之间的距离。因此,将执行的交换次数将减少。


      评论(0)问答(0)
      请先登录或注册

      请先登陆或注册

      相关推荐

      区块链底层加密算法之非对称加密

      区块链有四大要素分别是:分布式数据存储、点对点传输、共识机制、加密算法。对此很多读者都已经刷过了,但是为什么还是疑惑?因为四要素不是区块链的真相,只是区块链的四个特征,区块链另有自己的“中间层”。因此......
      社区菲菲 · 2020-02-26
      239阅读 · 0赞赏 · 0问答

      区块链加密算法介绍

      区块链提供了通过机器算法解决参与人之间的信任问题的全新方案,其核心的核心就是在不完全信任的各方,通过深度使用密码学算法来保证数据的不可篡改特性。比特币,谁能动我的钱比特币是公有链,账本分布在无中心的节......
      区块链论坛 · 2020-02-21
      462阅读 · 0赞赏 · 0问答

      密码学技术简介

      区块链使用的基本密码学技术包括哈希算法、对称加密、非对称加密和数字签名。本文将简单介绍各密码学的基本原理,仅限于概念性的内容,具体的原理、推导均未涵盖。希望能够带领大家了解密码学的基础要点。一、哈希算......
      链客 · 2020-02-21
      447阅读 · 0赞赏 · 0问答

      最新的密码学进展将改变区块链

      区块链公司Blockstream和数学家Andrew Poelstra的研究主管告诉Cointelegraph,零知识证明(ZK-Proof)系统是密码学领域“最令人兴奋的发展领域之一”。众所周知,这......
      论坛咸鸟 · 2020-02-21
      416阅读 · 0赞赏 · 0问答

      Rabbitmq和Kafka何时使用

      使用Kafka vs RabbitMQ是一个决定对您最终结果至关重要的决定,因此请继续阅读以了解更多有关这两个决定的信息,以便您充分了解情况。KafkaKafka是可用的领先消息代理之一,因为它可以在......
      波bobo · 2020-02-19
      508阅读 · 0赞赏 · 0问答

      AES-256加密是什么

      AES是高级加密标准的缩写。这是 美国政府用于加密敏感数据的对称  分组密码。个人和公司也都使用AES来锁定机密或其他有价值的信息。AES由国家标准技术研究院(NIST)创建  &......
      BTC · 2020-02-19
      472阅读 · 0赞赏 · 0问答

      16054

      LK币

      36

      粉丝

      406

      笔记

      感谢"区块链社区"

      这篇精彩的笔记,目前已经帮助

      • 1
      • 2
      • 7
      • 2
      • 3
      喜欢0
      链客社群 加入

      微博进入

      商务合作>

      广告投放>

      公司名称:北京链客行科技有限公司

      联系方式:010-67707199

      ICP备案号:京ICP备18032136号

      Copyright:链客区块链技术问答社区 版权所有

      感谢您的提问,问题被社区永久收入以便新人查看。一定要记得采纳最佳答案哦!加油!

      感谢您的善举,每一次解答会成为新人的灯塔,回答被采纳后获得20算力和相应的LK币奖励

      您将赞赏给对方2LK币的奖励哦!感谢您的赞赏!

      您将赞赏给对方2LK币的奖励哦!感谢您的赞赏!