冒泡排序算法任务单|新视野

说在前面

【资料图】

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

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

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

冒泡排序算法任务单（学生版）：任务1. 经典冒泡排序算法。已知数组d的初始值为[3, 2, 5, 4, 6, 1]，采用冒泡排序算法对其进行从小到大排序。（1）若采用向右扫描方式将最大值“冒泡”到右端，请写出每一趟排序后数组d的值。（2）若采用向左扫描方式将最小值“冒泡”到左端，请写出每一趟排序后数组d的值。（3）若采用向右扫描方式将最大值“冒泡”到右端，已知数组d的长度为n，请问总共需要排序多少趟？每趟比较次数分别为多少？总共比较次数为多少？（4）教材p131给出了采用向右扫描方式将最大值“冒泡”到右端的算法流程图和代码实现。但是由于排版的原因，代码实现与流程图并不完全一致（变量名称不同），请修改代码，使其与流程图保持一致，分别用for循环和while循环语句来实现程序功能。（5）若采用向左扫描方式将最小值“冒泡”到左端，请分别用for循环和while循环语句实现程序功能。体会将最小元素“上浮”和最大元素“下沉”两种方式在程序实现中的区别。

任务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记录当前元素的下标。

其实我们也可以从另一个角度来理解冒泡排序算法：假设当前数组中待排序序列为a[0:r+1]，其中r是序列的右边界；每趟排序都是从最左端开始向右扫描待排序区域，将最大值“冒泡”到a[r]处；r的初始值为len(a)-1，每完成一趟排序，就令r=r-1；当r=0时，待排序序列中只有一个元素，排序结束。参考代码如下，请将缺失的代码补充完整。

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趟。

观察排序过程，分析第一趟排序时，哪些元素的位置没有变化？最后一次交换操作发生在哪两个元素之间？。一般情况下，每排序一趟就将右边界r左移一位，能否在某趟排序之后，直接将右边界移动到正确位置，以快速缩小下一趟排序的扫描范围？我们可以设计一个冒泡排序的优化算法，通过记录最后一次发生交换操作的位置，把它作为下一趟排序的右边界，实现快速缩减扫描范围的目的。参考代码如下，请将缺失的代码补充完整。

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算法之旅文章分类

关键词： 冒泡排序 扫描方式 扫描范围