Coco学编程（三）－－冒泡就是折腾

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：唉~，那里又没有机会让我出场，失望啊，不知道哪天才能和大家再见面了，我会想你们的……