每日消息!冒泡排序算法任务单
说在前面
冒泡排序是经典排序算法之一,它通过对相邻两个元素依次进行比较和调整,让较大的元素“下沉”,较小的元素“上浮”来实现排序功能。冒泡排序的原理比较简单,一般经过教师的演示以后,学生都能根据指定的排序要求和扫描方向,写出每趟排序的过程。
(资料图片)
难点在于算法的代码实现。冒泡排序的核心代码是一个二重循环,其中内层循环描述了每轮排序的过程,根据扫描范围或方向的不同组合,可以产生各种不同的代码实现。如果学生不理解变量的含义,只会死记硬背的话,就容易产生张冠李戴的错误。如何让学生在纷繁复杂的变例拓展中抓住算法本质,是一个亟需解决的教学难题。
正确理解代码的关键在于明确变量的含义。运行一段程序就好比讲述一个故事,每个代码段都对应一个故事情节,关键变量就是故事中的主人公。变量的含义不同,其所在代码段的功能也就不一样。具体到冒泡排序算法,其核心代码是一个二重循环,赋予外层循环变量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算法之旅文章分类