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

 

# -*- 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