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