数据结构&算法实践—地精排序及改进

本网站用的阿里云ECS,推荐大家用。自己搞个学习研究也不错
本文作者: 伯乐在线wklken 。未经作者许可,禁止转载!
欢迎加入伯乐在线 专栏作者

排序>>交换排序>>地精排序

List:

1
2
3
4
0.概念+伪代码+示例分析
1.地精排序实现
2.改进
3.Question

  1. start

基本概念:

维基百科:http://en.wikipedia.org/wiki/Gnome_sort(目前只有英文版的)

地精排序又称侏儒排序,类似于插入排序,但是将一个数放入其正确位置的交换同冒泡排序(一系列交换)

简单,只有一层循环,

时间复杂度O(n^2),最优复杂度O(n),平均时间复杂度O(n^2)

其实思想很简单,往前冒泡,一旦发生数据交换,就往回冒泡,直到把被交换数字放入正确位置,之后,继续前进

伪代码(来自于维基百科)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
procedure gnomeSort(a[])
    pos := 1
    while pos < length(a)
        if (a[pos] >= a[pos1])
            pos := pos + 1
        else
            swap a[pos] and a[pos1]
            if (pos > 1)
                pos := pos 1
            else
                pos := pos + 1
            end if
        end if
    end while
end procedure

例子:

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
[5, 3, 2, 4]               #输入数组
 
i=0, i=i+1=1    #初始,i=0 ,直接i+=1
 
cmp l[0]= 5  l[1]= 3
change -> [3, 5, 2, 4]
swap, i=i1=0   #发生交换,i=i-1
 
i=0, i=i+1=1   #i=0,i+=1
 
cmp l[0]= 3  l[1]= 5
no swap, i=i+1=1   #无交换,i+=1
 
cmp l[1]= 5  l[2]= 2
change -> [3, 2, 5, 4]  #交换
swap, i=i1=1    #i=i-1,反向冒泡开始
 
cmp l[0]= 3  l[1]= 2
change -> [2, 3, 5, 4]
swap, i=i1=0  # 交换
 
i=0, i=i+1=1
cmp l[0]= 2  l[1]= 3
no swap, i=i+1=1 #无交换,i+=1
 
cmp l[1]= 3  l[2]= 5
no swap, i=i+1=2 #无交换,i+=1
 
cmp l[2]= 5  l[3]= 4
change -> [2, 3, 4, 5]
swap, i=i1=2  #交换,i-=1
 
cmp l[1]= 3  l[2]= 4
no swap, i=i+1=2
 
cmp l[2]= 4  l[3]= 5
no swap, i=i+1=3 #结束排序

1 start

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
#!/usr/bin/python
# -*- coding:utf-8 -*-
# 地精排序
#@author: wklken@yeah.net
 
def gnome_sort(l):
    i = 0
    while i < len(l):
        if i == 0 or l[i 1] < l[i]: #i=0或者正序不需交换,i+1
            i += 1
        else:  #否则,交换两数,i回退
            l[i 1], l[i] = l[i], l[i 1]
            i -= 1

  1. start

观察上面例子,是不是发现有些别扭…….

1
2
3
4
5
6
[3, 5, 2, 4]  #比较 5,2
[3, 2, 5, 4]  #交换
[3, 2,5, 4]  #比较 3,2
[2, 3, 5, 4]  #交换
[2, 3, 5, 4]    #比较2,3
[2, 3, 5, 4]    #比较3,5

没错,若是到了b存在交换,反向冒泡,直至把被交换数冒泡放到其有序位置a,然后再从a->b进行比较冒泡

其实,a->b这一段序列已经是有序的,不需要浪费比较次数在这上面

所以我们进行jump

即,记录b的位置,当发现反序冒泡没有交换时(冒泡结束),jump到b位置,继续正序冒泡

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def gnome_sort2(l):
    i = 0
    current_index = 0  #保存反向冒泡前位置
    back_noswap = True  #标识反向冒泡是否完成
    while i < len(l):
        if i == 0 or l[i 1] < l[i]: #i=0或者正序不需交换,i+1
            i += 1
            back_noswap = True
        else:  #否则,交换两数,i回退
            l[i 1], l[i] = l[i], l[i 1]
            current_index = i + 1  #开始反序,记录位置,跳转回来后比较就是 i i+1两个数的比较,之前数已有序
            back_noswap = False
            i -= 1
            print “change ->”, l
        if current_index and back_noswap:  #满足 当前是反序冒泡,且未发数据交换,代表已结束,可以跳回
            i = current_index
            current_index = 0
            print “jump”,i

实际过程:

1
[5, 3, 2, 4]

cmp 5 3

1
2
change -> [3, 5, 2, 4]
jump 2   #这里jump的位置是i+1

cmp 5 2

1
change -> [3, 2, 5, 4]

cmp 3 2

1
change -> [2, 3, 5, 4]

jump 2
cmp 3 5
cmp 5 4

1
change -> [2, 3, 4, 5]

cmp 3 4
jump 4

相同例子的序列,改进前比较次数12,改进后只需要9次

  1. start

A.地精排序概念,过程描述?

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

C.适用场景,何种情况下表现最优

打赏支持我写出更多好文章,谢谢!
打赏作者

打赏支持我写出更多好文章,谢谢!

任选一种支付方式

1 赞
3 收藏

评论





关于作者:wklken


Pythonista/vimer


个人主页 ·
我的文章

· 36 ·   

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

未经允许不得转载:演道网 » 数据结构&算法实践—地精排序及改进

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

评论 0

评论前必须登录!

登陆 注册