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

List:

0.概念+伪代码+示例分析
1.地精排序实现
2.改进
3.Question
  1. 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
  1. 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位置,继续正序冒泡

代码:

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次

  1. start

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

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

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