7.6 希尔排序★3◎4

7.6 希尔排序★3◎4


7.6 希尔排序★3◎4
  希尔排序又称缩小增量排序,是1959年由D.L.Shell提出来的,较上述几种插入排序方法有较大的改进。

 …

7.6 希尔排序★3◎4

7.6 希尔排序★3◎4

  希尔排序又称缩小增量排序,是1959年由D.L.Shell提出来的,较上述几种插入排序方法有较大的改进。
  希尔排序的基本思想:
  (1)选择一个步长序列t1,t2,…,ti-1,ti,…,tk,其中,ti-1>ti,tk=1;
  (2)按步长序列个数k,对序列进行k趟排序;
  (3)每趟排序,根据对应的步长ti,将待排序列分割成若干长度为m的子序列,分别对各子表进行直接插入排序。仅步长因子为1时,整个序列作为一个表来处理,表长度即为整个序列的长度。
  设待排序列为39,80,76,41,13,29,50,78,30,11,100,7,41,86。步长因子分别取5、3、1,则排序过程如下:

  子序列分别为{39,29,100},{80,50,7},{76,78,41},{41,30,86},{13,11}。
  第一趟排序结果:

  子序列分别为{29,30,50,13,78},{7,11,76,100,86},{41,39,41,80}。
  第二趟排序结果:
  p=1 13 7 39 29 11 41 30 76 41 50 86 80 78 100
  此时,序列基本“有序”,对其进行直接插入排序,得到最终结果:

7 11 13 29 30 39 41 41 50 76 78 80 86 100

【效率分析】
  希尔排序时效分析很复杂,因为关键码的比较次数与记录移动次数依赖于步长因子序列的选取,但特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有选取最好的步长因子序列的方法。步长因子序列可以有各种取法,有取奇数的,也有取质数的,但需要注意:步长因子中除1外没有公因子,且最后一个步长因子必须为1。希尔排序方法是一个不稳定的排序方法。
 

7.6 希尔排序★3◎4

    关于作者: admin

    这里可以再内容模板定义一些文字和说明,也可以调用对应作者的简介!或者做一些网站的描述之类的文字活着HTML!

    为您推荐

    发表评论

    电子邮件地址不会被公开。 必填项已用*标注

    评论列表 人参与

    联系我们

    联系我们

    8888-88888888

    在线咨询: QQ交谈

    邮箱: email@admin.com

    工作时间:周一至周五,9:00-17:30,节假日休息

    关注微信
    微信扫一扫关注我们

    微信扫一扫关注我们

    关注微博
    返回顶部