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

本网站用的阿里云ECS,推荐大家用。自己搞个学习研究也不错
排序>>交换排序>>梳子排序

List:

1
2
3
0.概念+伪代码+示例分析
1.梳子排序实现
2.Question

  1. start

基本概念:

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

伪代码

1
2
3
4
function comb_sort(A: list[1..n]){
    gap = A.size
    rate = 1.3
    while gap  1

梳子排序:

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

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

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

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

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

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

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

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

1
[8, 4, 3, 7, 6, 5, 2, 1]

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

1
2
3
4
5
cmp l[0]=8,l[6]=2
change [2, 4, 3, 7, 6, 5,8, 1]
cmp l[1]=4,l[7]=1
change [2, 1, 3, 7, 6, 5, 8,4]
one time: [2, 1, 3, 7, 6, 5, 8, 4]

gap: 4

1
2
3
4
5
6
cmp l[0]=2,l[4]=6
cmp l[1]=1,l[5]=5
cmp l[2]=3,l[6]=8
cmp l[3]=7,l[7]=4
change [2, 1, 3, 4, 6, 5, 8,7]
one time: [2, 1, 3, 4, 6, 5, 8, 7]

gap: 3

1
2
3
4
5
6
cmp l[0]=2,l[3]=4
cmp l[1]=1,l[4]=6
cmp l[2]=3,l[5]=5
cmp l[3]=4,l[6]=8
cmp l[4]=6,l[7]=7
one time: [2, 1, 3, 4, 6, 5, 8, 7]

gap: 2

1
2
3
4
5
6
7
cmp l[0]=2,l[2]=3
cmp l[1]=1,l[3]=4
cmp l[2]=3,l[4]=6
cmp l[3]=4,l[5]=5
cmp l[4]=6,l[6]=8
cmp l[5]=5,l[7]=7
one time: [2, 1, 3, 4, 6, 5, 8, 7]

gap: 1

1
2
3
4
5
6
7
8
9
10
11
cmp l[0]=2,l[1]=1
change [1,2, 3, 4, 6, 5, 8, 7]
cmp l[1]=2,l[2]=3
cmp l[2]=3,l[3]=4
cmp l[3]=4,l[4]=6
cmp l[4]=6,l[5]=5
change [1, 2, 3, 4, 5,6, 8, 7]
cmp l[5]=6,l[6]=8
cmp l[6]=8,l[7]=7
change [1, 2, 3, 4, 5, 6, 7,8]
one time: [1, 2, 3, 4, 5, 6, 7, 8]

观察上面例子,梳排序可以有效地将乌龟(尾部的小数值和头部的大数值)调整到有序后位置的附近

  1. start
    :::python
    def comb_sort(l):
    dis = int(len(l)/1.3)
    while dis:
    for i in range(len(l)-dis):
    if l[i] > l[i+dis]:
    l[i], l[i+dis] = l[i+dis], l[i]
    dis = int(dis/1.3)

2 start

A.奇偶排序概念,过程描述?

B. 时间复杂度?空间复杂度?是否是稳定排序?

C.适用场景

转载自演道,想查看更及时的互联网产品技术热点文章请点击http://go2live.cn

未经允许不得转载:演道网 » 数据结构&算法实践—梳子排序

赞 (0)
分享到:更多 ()