Skip to content

《程序语言的奥妙》之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], []]"

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.