数据结构&算法实践—【排序|交换排序】地精排序及改进

排序»交换排序»地精排序

List:

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

0. start

基本概念:

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

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

简单，只有一层循环，

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

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

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

procedure gnomeSort(a[])
    pos := 1
    while pos < length(a)
        if (a[pos] >= a[pos-1])
            pos := pos + 1
        else
            swap a[pos] and a[pos-1]
            if (pos > 1)
                pos := pos - 1
            else
                pos := pos + 1
            end if
        end if
    end while
end procedure

例子：

[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=i-1=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=i-1=1    #i=i-1，反向冒泡开始

cmp l[0]= 3  l[1]= 2
change -> [2, 3, 5, 4]
swap, i=i-1=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=i-1=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

#!/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

2. start

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

[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位置，继续正序冒泡

代码:

:::python
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    

实际过程：

[5, 3, 2, 4]

cmp 5 3

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

cmp 5 2

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

cmp 3 2

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

jump 2 cmp 3 5 cmp 5 4

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

cmp 3 4 jump 4

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

3. start

A.地精排序概念，过程描述？

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

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