欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-08 21:21:04
...

 

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