学算法与Python之不求甚解——Shell排序

84366992

# -*- coding:gb2312 -*-
'''
Created on 2010-7-29
@author: http://g-content.appspot.com
'''
#希尔排序
#定义一个数组
#lst = [81, 94, 11, 96, 12, 24, 17, 95, 28, 58, 41, 75, 15]
lst = [81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15]
ord = [5, 3, 1]
for i in ord:
#按当前序列值进行循环分组排序
for o in range(len(lst)):
#得到分组序号
grp = range(o, len(lst), i);
if len(grp) <= 1:
break;
#对当前分组进行插入排序
for c in range(1, len(grp)):
#获得当前分组最后一个值
last = lst[grp[c]]
#插入排序第n趟序列
n = range(1, c + 1)
#从右到左比较
n.reverse()
for f in n:
'''
由于n是针对分组的序列，所以实际值是lst[grp[f]]
'''
if lst[grp[f]] < lst[grp[f - 1]]:
lst[grp[f]] = lst[grp[f-1]]
lst[grp[f-1]] = last
print '第',i,'排序是',lst