Coco：好久不见，真想大家。由于某人的懒惰，严重影响到到我的人气啊。
我：还好意思说，前段时间我本来是感冒，却让你宣扬成了“某种未知的呼吸系统传染病”，害得我差点被隔离。
Coco：不把你隔离起来，怎么能让你老老实实的写文章？
我：隔离我也认了，你居然会造谣说我的病会在QQ上传染，难道你要我被隔离到一个不能上网的地方吗？什么时候听说过人类的传染病会能过互联网传染了？
Coco：所以说我说你中的是CIH呀~
我：@#$%^
什么时候人能中CIH了~
Coco：不可能吗？
我：可能吗？
Coco：不可能吗？
我：可能吗？
Coco：不可能吗？
我：可能吗？
Coco：我只是探讨一下，不要那么激动嘛，不可能吗？
我：要是我哪天我能中了CIH，干脆找人把我格式化了重装算了。
Coco：别忘了装套Linux，都说这东东好，我还没用过呢。
我：喂喂喂，我们再这么胡扯下去，篇幅就都被浪费啦。
Coco：好吧好吧，戴上口罩，继续工作。这次我们玩儿什么？
（玩……还真是一语中的啊，本来要把你包装成一个积极向上的好青年的，这下大家都知道你学Python是为了好玩儿了……）
我：我们这次玩儿……不对，是要学习一个很亲切的排序算法，冒泡排序。
Coco：这个~是不是太简单了？好像很多人写过Hello World之后第二个程序就是这个东东了。
我：这倒是不假，冒泡排序的特点就是实现非常简单，基本上所有有流程控制能力的语言都可以实现它，而且也非常容易学习，可以说这是算法课的“Hello World”。在Python中的实现也不会比其它语言更复杂。现在你写一个冒泡来对我们一直用的示例数组排序吧。
Coco：没有你的日子里，我寂寞无聊中，自己写了一些程序，其中就包括这个冒泡~
我：喂~，不要说得那么肉麻好不好？让人以为我们有什么不可告人的关系……先把程序拿来给我看看。
def BubSort(theInput):
#c = 0
#e = 0
for i in range(len(theInput)):
for j in range(1, len(theInput) - i):
if theInput[j-1] > theInput[j]:
theInput[j-1], theInput[j] = theInput[j], theInput[j-1]
#e = e + 1
#c = c + 1
#print c
#print e
return
#Follow is the demo of Bubble up sort.
Array=[6, 16, 10, 9, 15, 5, 11, 1, 19, 4, 14, 17, 18, 0, 13, 3, 12, 2, 8, 7]
print Array
BubSort(Array)
print Array
Coco：那些注释中的代码好像与我无关啊？
我：这是我给你加上的。你的代码本身没什么问题，运行良好。我加上这些代码是为了计算一下排序中进行了多少次操作。只要把关于c的代码行注释符去掉，就可以计算发生了多少次交换，把关于e的代码行注释符去掉，就可以计算生发生了多少次比较。
Coco：好像很方便的样子，我试试喽。才20个元素的列表，应居要190次比较和108次交换啊。
我：事实上，在这个程序中，比较次数只和元素的个数有关，N个元素的比较次数就是N*(N+1)/2。即使是一个完全排好序，不需要再进行交换的数组。
Coco：我用[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]试试……还真是这样子呢。这岂不是做了很多无用功？
我：是呀，针对这个问题，你有没有什么好办法呢？
Coco：我想，可以记住每次遍历中最后一次发生交换的位置，下次搜索到这个位置为止就好了，我在程序里加一个标志试试。
def MrkBubSort(theInput):
# c = 0
# e = 0
i = 0
bottom = len(theInput)
while i < bottom:
i = 0
M = True
for j in range(1, bottom):
if theInput[j-1] > theInput[j]:
theInput[j-1], theInput[j] = theInput[j], theInput[j-1]
M = False
bottom = j
# e = e + 1
# c = c + 1
if M:
break
i = i + 1
# print c
# print e
return
#Follow is the demo of Bubble up sort.
Array=[6, 16, 10, 9, 15, 5, 11, 1, 19, 4, 14, 17, 18, 0, 13, 3, 12, 2, 8, 7]
print Array
MrkBubSort(Array)
print Array
Coco：把注释掉的计数代码拿出来运行后可以知道，对同样的这个数组，发生了178次比较，确是少了一些啊。
我：如果你试一试一些“极端”的数据，会观察到一些有趣的现像。比如 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]，[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 0]，[19, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]，[19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]等等。
Coco：以下是输出结果，每一组输出结果中，第一组是原数组，下一行的单个整数是比较次数，下一个是交换次数，最后一行的数组是排序后的。
>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
19
0
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
>>>
>>> [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
190
190
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
>>> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 0]
190
19
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
>>>
>>> [19, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
37
19
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
Coco：的确是有一些问题，比如，如果数组的未尾存在逆序，即使前面的数据已经排好，也一样需要190次交换。有没有什么办法解决它呢？
我：提示一下，如果逆序在开头呢？
Coco：嗯，只需要37次比较。看来比较次数和操作的方向有关。
我：所以，如果从两端交替进行排序，就可以尽可能的避免无谓的比较操作。这种算法我们称为摇动。你试试实现它吧。
（很长时间后……）
def ShkBubSort(theInput):
c = 0
e = 0
l = len(theInput)
tmpt = 1
top = 0
tmpb = l
bottom = tmpb
while top < bottom:
if top < tmpt:
top = tmpt
else :
top = top + 1
bottom = tmpb
M = True
for j in range(top, bottom):
if theInput[j-1] > theInput[j]:
theInput[j-1], theInput[j] = theInput[j], theInput[j-1]
M = False
tmpb = j
e = e + 1
c = c + 1
if M:
break
for k in range(top + 1, bottom):
cur = l - k
if theInput[cur - 1] > theInput[cur]:
theInput[cur-1], theInput[cur] = theInput[cur], theInput[cur-1]
M = False
tmpt = cur
e = e + 1
c = c + 1
if M:
break
# print top, bottom
print c
print e
return
Coco：比我想像的麻烦的多啊。实际效果如何呢？我试试。
>>> [19, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
54
19
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
>>> [6, 16, 10, 9, 15, 5, 11, 1, 19, 4, 14, 17, 18, 0, 13, 3, 12, 2, 8, 7]
169
108
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
>>>
>>> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 0]
54
19
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
>>> [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
190
190
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
Coco：总的来说，好像有些改进，不过并不是很明显噢。
我：实际上，最关键的是，不论如何改进，都不会改变这一系列算法交换操作过多的缺点。而在排序操作中，写操作的代价要远高于读操作，所以无论怎样减少比较次数，都不能真正有效的提高排序的效率。
Coco：唉，费这么大劲，学了一个不甚实用的算法，真是瞎折腾……
我：当然，学习这个算法……
Coco：OK，OK，我知道你要说，主要是为了让我练习，不过现在每个月只露一次面，无论多复杂的程序，也不能真正有效的提高我的熟练程度啊。你是不是也应该勤劳一些呀~
我：事实上，这个月我可没有让大家空等。我一直在写《SQL Story》的第十一集，现在基本上已经解决了所有的问题，很快就会完成。
Coco：唉~，那里又没有机会让我出场，失望啊，不知道哪天才能和大家再见面了，我会想你们的……
本文地址：http://com.8s8s.com/it/it29261.htm