扫描二维码,下载手机APP
下载安卓APP箭头
客服QQ
箭头给我发消息

客服QQ:3315713922
论坛 >编程语言 >数据结构&算法实践—梳子排序

数据结构&算法实践—梳子排序

课课家iOS游客发布于 2018-04-18 09:27查看:10865回复:6

排序>>交换排序>>梳子排序

List:

image.png

  1. start

基本概念:

维基百科http://zh.wikipedia.org/wiki/%E6%A2%B3%E6%8E%92%E5%BA%8F

伪代码

image.png

梳子排序:

间隔gap 递减率rate(大于1的数)

比较 i 和 i+gap 位置的数字,若反序,交换,然后i+=1,直到比较i+gap超过最大索引

然后gap /= rate,再重复上面操作

直到gap=1 ,执行最后一遍梳理后结束

可以想象成 先拿一把大梳子(只有三个齿两个缝的)从第一个梳到最后一个,把两个缝隙里面反序的数交换

再换把小点的梳子,重复.

最终,中间那个齿消失(梳理相邻两个数),完成最后一遍梳理

例子:(关注gap和cmp的下标)

image.png

gap: 6 [初始设定gap=size/1.3]

image.png

gap: 4

image.png

gap: 3

image.png

gap: 2

image.png

gap: 1

image.png


收藏(0)0
查看评分情况

全部评分

此主贴暂时没有点赞评分

总计:0

回复分享

版主推荐

    共有6条评论

    • 课课家运营团队
    • Mr ken
    • YUI
    • cappuccino
    • mr jack
    • IT宅男
    • Mright
    • 课课家软考1
    • 选择版块:

    • 标题:

    • 内容

    • 验证码:

    • 标题:

    • 内容

    • 选择版块:

    移动帖子x

    移动到: