冒泡排序算法任务单

说在前面

冒泡排序是经典排序算法之一，它通过对相邻两个元素依次进行比较和调整，让较大的元素“下沉”，较小的元素“上浮”来实现排序功能。冒泡排序的原理比较简单，一般经过教师的演示以后，学生都能根据指定的排序要求和扫描方向，写出每趟排序的过程。

难点在于算法的代码实现。冒泡排序的核心代码是一个二重循环，其中内层循环描述了每轮排序的过程，根据扫描范围或方向的不同组合，可以产生各种不同的代码实现。如果学生不理解变量的含义，只会死记硬背的话，就容易产生张冠李戴的错误。如何让学生在纷繁复杂的变例拓展中抓住算法本质，是一个亟需解决的教学难题。

正确理解代码的关键在于明确变量的含义。运行一段程序就好比讲述一个故事，每个代码段都对应一个故事情节，关键变量就是故事中的主人公。变量的含义不同，其所在代码段的功能也就不一样。具体到冒泡排序算法，其核心代码是一个二重循环，赋予外层循环变量i不同的含义，我们就可以从不同的角度叙述冒泡排序的故事。

任务2. 冒泡排序优化。

经典的冒泡排序算法，对长度为n的数组需要排序n-1趟。

例如，对数组a=[5,1,3,4,2,6,7,8],需要向右扫描排序7趟，每趟排序结果如下：

第1趟：[1,3,4,2,5,6,7,8]

第2趟：[1,3,2,4,5,6,7,8]

第3趟：[1,2,3,4,5,6,7,8]

第4趟：[1,2,3,4,5,6,7,8]

第5趟：[1,2,3,4,5,6,7,8]

第6趟：[1,2,3,4,5,6,7,8]

第7趟：[1,2,3,4,5,6,7,8]

（1）仔细观察排序过程，我们可以发现第3趟冒泡后数组已经有序，后面4趟排序实际上没有做任何交换操作。当数组已经有序时，能否提前结束排序，不再做无必要的扫描？我们可以设置一个标记变量flag来标记某趟排序过程中是否发生了交换操作，若无交换操作，表示已完成排序，退出循环。 

def bubble_sort_3(a):

    for i in range(1, len(a)):

        swapFlag = False #先假设未做交换操作

        for j in range(len(a)-i):

            if a[j] > a[j+1]:

                a[j], a[j+1] = 填空1

                swapFlag = 填空2 #设置交互操作标志

        if 填空3: #无交换操作，表示已完成排序，退出循环

            break  

（2）当采用向右扫描方式将最大值“冒泡”到右端时，经典的代码实现是设置二重for循环，其中外层循环变量i记录排序趟数，内层循环变量j记录当前元素的下标。

def bubble_sort_4(a):

    for r in range(len(a)-1, 0, -1):

        for j in range(填空1): #向右扫描，将最大值冒泡到a[r]

            if 填空2 :

                a[j], a[j+1] = a[j+1], a[j]

（3）使用函数bubble_sort_4(a)对数组a=[5,1,3,4,2,6,7,8]排序，每趟排序只让右边界r左移1位，总共需要排7趟。

def bubble_sort_5(a):

    right = len(a)-1

    while 填空1:

        swapPos = 0 #先假设最后一次发生交换操作的位置为0

        for j in range(right): #顺序扫描a[0:right]

            if a[j] > a[j+1]:

                a[j], a[j+1] = a[j+1], a[j]

                swapPos = 填空2 #记录发生交换操作的位置

        right = 填空3

（4）向右扫描时，可以设置右边界，通过更新右边界，实现快速缩减扫描范围的目的。那么，能否在向左扫描时，通过快速更新左边界来提高程序效率呢？请模仿函数bubble_sort_5(a)，编写向左扫描数组将最小值“冒泡”到左端的冒泡排序优化算法。

（5）既然向右扫描时可以设置右边界，向左扫描时可以设置左边界，分别都可以快速缩小扫描范围。那么能否更进一步，在内层循环中向左、向右各扫描一次，分别设置左、右边界呢？

当然可以。这种算法被称为双向冒泡排序，又称鸡尾酒排序，每轮扫描下来可以更新左、右边界，快速减少扫描范围，提高了程序效率。

def bubble_sort_7(a):

    left, right = 0, len(a)-1

    while 填空1:

        swapPos = left #先假设最后一次发生交换操作的位置为left

        for j in range(left,right): #顺序扫描a[left:right]

            if a[j] > a[j+1]:

                a[j], a[j+1] = a[j+1], a[j]

                swapPos =填空2

        right =填空3

        for j in range(right,left,-1): #逆序扫描a[left+1:right+1]

            if a[j] < a[j-1]:

                a[j],a[j-1] = a[j-1],a[j]

                swapPos =填空4

        left =填空5

冒泡排序算法采用双重for循环嵌套来实现，外层循环用来控制排序轮次（或待排序区间左边界），内层循环通过交换相邻元素的方式，将较小值向左侧冒泡。在每一轮排序结束后，都要把最小值冒泡到待排序区间最左端。

冒泡排序的比较次数与待排序元素的初始状态无关，共需要进行的比较次数是(n–1)+(n–2) + … +2+1 = n*(n–1)/2 。

冒泡排序的交换次数与待排序元素的初始状态有关，序列中逆序对的数量就等于排序过程中的交换次数。

可以使用设置交换操作标记、快速缩小右边界和双向冒泡排序等优化方法来提高冒泡排序的效率。

需要本文word文档、源代码和课后思考答案的，可以加入“Python算法之旅”知识星球参与讨论和下载文件，“Python算法之旅”知识星球汇集了数量众多的同好，更多有趣的话题在这里讨论，更多有用的资料在这里分享。

我们专注Python算法，感兴趣就一起来！

相关优秀文章：

阅读代码和写更好的代码

最有效的学习方式

Python算法之旅文章分类