侏儒排序算法原理与Python实现

算法原理：假设一个人沿列表从头到尾走，如果发现有相邻元素顺序不对的就交换一下，然后后退一步，否则继续往前走，当走到列表尾部时，所有元素就排好序了。

import random

def gnomeSort(lst):

i = 0

length = len(lst)

while i < length:

#回头看，如果当前元素比前面的大或者相等，就继续往前走

if i==0 or lst[i-1]<=lst[i]:

i += 1

else:

#如果当前元素比前面的小，就交换位置，然后后退一步

lst[i-1], lst[i] = lst[i], lst[i-1]

i -= 1

lst = list(range(20))

random.shuffle(lst)

print(lst)

gnomeSort(lst)

print(lst)