排序>>交换排序>>梳子排序
List:
|
1 2 3 |
0.概念+伪代码+示例分析 1.梳子排序实现 2.Question |
- 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] |
观察上面例子，梳排序可以有效地将乌龟（尾部的小数值和头部的大数值）调整到有序后位置的附近
- 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.适用场景
