mzh/blog

《程序语言的奥妙》之Python实现--Part1

还有很多对于计算机概念的有趣解释,大家就自己看吧 :)

进入正题

前面就介绍下这本书,接下来是里面各种经典算法的Python实现,问题和算法神马的大家看书就好了~我就不摘抄了。 有错欢迎指正。

第47节:辗转相除法

或称欧几里得求最大公约数算法

#!/usr/bin/env python
# encoding: utf-8

def Euclid(x, y):
    if x < y:
        tmp = x
        x = y
        y = tmp

    while y != 0:
        rod = x % y
        x = y
        y = rod
    return x

if __name__ == '__main__':
    print Euclid(126, 90) # should be 18

第50节:桶排序

#!/usr/bin/env python
# encoding: utf-8

def bucket_sort(lis):

    max_item = max(lis)
    bucket = [-1 for x in xrange(max_item+1)]

    for item in lis:
        if item < 0:
            raise ValueError("Can't handle %d" % item)
        bucket[int(item)] = item

    return filter(lambda x: x != -1, bucket)

if __name__ == '__main__':
    print bucket_sort([8,2,1,5,9,7])  # should be [1,2,5,7,8,9]

第51节:基位排序—-桶排序的升级版

#!/usr/bin/env python
# encoding: utf-8
from copy import deepcopy

def bit_sort(lis):

    bucket = [[] for x in xrange(len(lis))]
    k = len(str(max(lis))) # sort time
    array = [deepcopy(bucket) for x in xrange(k)]

    for time in xrange(k):
        if time == 0:
            for l in lis:
                array[0][int(str(l)[-1])].append(l)
        else:
            for b in array[time-1]:
                for item in b:
                    try:
                        array[time][int(str(item)[-1-time])].append(item)
                    except IndexError:
                        array[time][0].append(item)
    return array

if __name__ == '__main__':
    for line in bit_sort([123, 602, 82, 777, 57, 510, 396, 196, 843, 138]):
        print line
    print "The Last line should be:[[57, 82], [123, 138, 196], [], [396], [], [510], [602], [777], [843], []]"