冒泡排序算法的几种优化与变形_胡伟东.pdf

2023.4电脑编程技巧与维护1概述排序是数据处理中经常使用的运算方法。例如，电子邮件列表按照日期排序；购物网站上搜索到的某类商品按价格、销售等方式进行排序。冒泡排序是经典的排序算法之一。冒泡排序是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉（上冒）”、让较小的数“上冒（下沉）”的一种排序技术。以升序为例，冒泡排序算法将待排序的n个数中相邻两个数进行比较，将较大的数交换到后面的一个位置上。重复这一操作，直到处理完本轮数列中最后两个元素，称为一轮排序。当一轮排序完成时，最大的数就被轮换到本轮排序数列最右端位置上。重复上面的过程，经过n-1轮后，就实现了数据升序排序。在以下的算法中，使用Python语言实现排序。2传统冒泡排序假定序列中有n个数，要进行从小到大的排序。若参与排序的数组元素共有n个，则需要n-1轮排序。在第i轮排序中，从左端开始，相邻两数比较大小，若反序则将两者交换位置，直到比较第n+1-i个数为止。第1个数与第2个数比较，第2个数和第3个数比较，一直到第n-i个数与第n+1-i个数比较，一共处理n-i次。此时，第n+1-i个位置上的数已经有序，后续就不需要参加以后的排序。（1）第1轮冒泡排序先从第1个数和第2个数开始比较，若第1个数大于第2个数，则需要交换两者的位置；否则保持不变。重复这一过程，直到处理完本轮数列中最后两个数。（2）第2轮冒泡排序与第1轮冒泡排序进行相同的排序，使大的数交换到n-2的位置上。（3）重复以上过程，共需经过n-1轮冒泡排序后，数据实现升序排序。例如，序列26，28，24，11，排序过程如表1所示。具体排序算法如下。for i in range(1,n):for j in range(0,n-i):if ajaj+1:aj,aj+1=aj+1,aj外循环：即主循环，其中i为本轮排序的左端点，需要将本轮的最大值移到右端点，需要处理n-1轮，如果可以保证前n-1个元素都交换到正确的位置上，那么最后一个数就是有序的，不需要进行处理。内循环：即副循环，通过内循环将相邻元素进行比较和换位，把大的数往后移，一直循环n-1-i轮这样可以将最大的数移到右端，而有序的数就不用再比较了。对n个元素用冒泡排序进行排序时，共需比较次数如公式（1）所示：（1）其时间复杂度为O（n2）。对于序列6，3，1，4，3，前面的数字“3”和后面的数字“3”的顺序在整个冒泡排序过程中始终没有发生变化，即冒泡排序并不产生新的逆序对。如果两个元素相等，则相等元素的前后顺序不改变。因此，冒泡排序是一种稳定的排序算法。3优化 1标志法对于序列1，2，3，5，4，在第1轮冒泡排序作者简介：胡伟东，男，硕士，一级教师。冒泡排序算法的几种优化与变形胡伟东（绍兴鲁迅中学，浙江 绍兴312000）摘要：冒泡排序是一种经典的排序算法。根据冒泡排序的原理，总结了通过 flag 控制判断某轮排序是否有序、当有序时就提前结束循环的标志法，并通过记录每次排序最后一次交换位置，优化排序区间的区间控制法。同时根据冒泡排序的特点，总结了冒泡排序的变形、双向冒泡排序、分组冒泡排序和交替冒泡排序。关键词：冒泡排序；优化；变形轮数a0a1a2a3026282411126241128224112628311242628表14数排序过程51DOI:10.16184/prg.2023.04.0322023.4电脑编程技巧与维护后，序列仍为1，2，3，4，5，进而发现后续3轮中都没有发生数据交换，即其实不用再执行后面的几轮。算法只需要执行到某轮排序不需要交换数据即可。在原来的程序中，加上一个标志变量flag，用于记录在这一趟排序中是否发生了数交换。如果某轮结束后flag的值为False，则说明本轮没有交换行为，数据已经全部有序，可以提前结束排序，具体如下。（1）在第1轮冒泡排序中首先比较第1个数和第2个数，若前者大于后者，则交换两者位置，同时flag=True；否则不换。重复这一过程，直到处理完最后两个数据。（2）如果flag=False，则结束循环；否则重复上述过程。具体算法如下。flag=Truefor i in range(1,n):flag=Falsefor j in range(0,n-i):if ajaj+1:aj,aj+1=aj+1,ajflag=Trueif not flag:break4优化 2区间控制法对于序列2，3，4，5，9，8，7，采用“上冒”，第一轮排序结束后 2，3，4，7，9，8。当7和9交换位置后，后续的数字都没有互换，即在后续的排序中2，3，4，7不需要参与排序。得出结论：每轮遍历的区间边界都是由上一轮遍历最后一次发生交换的位置决定的。这样一来，可以引入标记变量last记录每轮排序最后一次交换的位置，并将last赋给下一轮遍历区间的终点。大大缩小了下一轮排序遍历区间，快速收缩待排序范围，从而提高了算法效率。例如，序列2，3，4，5，9，8，7，排序过程如表2所示。通过区间控制法，可以快速地结束排序。（1）第1轮冒泡排序先比较第n-1个数和第n-2个数，若前者大于后者，则交换两者位置，同时记录最后一次交换的位置last，重复这一过程，直到处理完数组中最后两个元素中的数据。（2）下一轮排序从n-1至last，重复上面的过程，直到结束循环。具体排序算法如下。i=1while in:last=n-1for j in range(n-1,i-1,-1):if ajaj-1:aj,aj-1=aj-1,ajlast=ji=last+15变形 1双向冒泡法从经典的冒泡算法中可以发现，经典的冒泡排序是从一端开始比较的，经过第1轮排序后，一端为极值点，如此重复处理完成排序。换角度思考，在实现一端有序的同时，从另一端也进行排序，使另一端也为极值点，即实现双向冒泡排序。（1）第1轮从左向右，将最大值移到右端点。（2）第2轮从右向左，将最小值移到左端点。（3）重复上述过程，数据实现交替排序。例如，序列 79，13，93，55，29，17，排序过程如表3所示。具体算法如下：left=0;right=n-1while leftaj+1:aj,aj+1=aj+1,ajright=jfor j in range(right,left,-1):if ajaj-1:aj,aj-1=aj-1,ajleft=j6变形 2分组冒泡法经典的冒泡排序是对整个数列由小到大或由大到小进行排序，但是有时需要对数组元素进行隔位排序，如图1所示。轮数a0a1a2a3a4023459a5a6871234579822345789表27个数排序过程轮数a0a1a2a3a4a50791393552917113177955299321317295579933131729557993表36个数排序过程522023.4电脑编程技巧与维护三轮排序后结果如图2所示。实现了索引偶数位升序排序、奇数位降序排序。例如，序列79，13，93，55，29，17，排序过程如表4所示。（1）第1轮冒泡排序首先比较第1个数和第3个数，若前者大于后者，则交换两者位置；否则不换位置。其次比较第2个数和第4个数，若前者小于后者，则交换两者位置，否则不需要交换。反复这一过程，直到处理完本轮最后两个数。（2）重复上述处理过程，数据实现排序。具体算法如下。for i in range(1,n/2+1):k=1for j in range(0,n-2-2*i):if k*ajk*aj+2:aj,aj+2=aj+2,ajk=-k在程序中，通过变量k来控制升序和降序。7变形 3交替冒泡法对于数组，按最小、最大、第2小、第2大、第3小、第3大排序。例如，数组a=8，1，2，6，3，4，7，5。（1）第1轮从右向左排序，将最小值移到左端点。（2）第2轮从右向左排序，将最大值移到左端第2个位置。（3）重复上述过程，共经过n-1轮冒泡排序后，实现数据交替排序。例如，序列79，13，93，55，29，17，排序过程如表5所示。具体算法如下：for i in range(1,n):k=1for j in range(n-1,i-1,-1):if k*ajk*aj-1:aj,aj-1=aj-1,ajk=-k在程序中，通过变量k来控制极值。8结语通过对冒泡排序优化与变形的总结，提高了学生自行总结冒泡算法知识和运用冒泡算法的能力，将“死记硬背”的程序转化为属于学生的编程能力，同时训练了学生的计算思维，提高了课堂教学效率。在一系列冒泡算法优化与变形活动中，学生慢慢地理解冒泡算法的核心思想，提升了理解程序、解决问题的能力。冒泡排序虽然有多种优化和变形，在一定程度上给教师的教学和学生的学习造成了困难，但是只要抓住冒泡排序的核心思想，就能提高学生提炼算法和运用算法的能力。将学生背下来的程序转化为真正属于他们的程序，同时锻练了学生的思维能力，提升学生的信息技术核心素养。参考文献1张乃孝算法与数据结构C语言描述M 2版.北京:高等教育出版社,20082潘颖利用往返比较改进冒泡排序算法J 科技信息,2007(29):404-405.3王晓东计算机算法设计与分析M 3版.北京:电子工业出版社,20034杨朝霞分析和计算算法效率的便捷方法J 兰州交通大学学报,2004(4):78-82.5孙立会,周丹华.国际儿童编程教育研究现状与行动路径J.开放教育研究,2019,25(2):23-35.6林玉慈.高中数学课程中的逻辑推理及教学策略研究D.长春:东北师范大学,2019.7陶增乐.普通高中课程标准实验教科书信息技术基础必修M.杭州：浙江教育出版社,2016.图1数组元素隔位排序图2三轮排度后结果轮数a0a1a2a3a4a5079139355291717955291793132295579179313表46个数隔位排序过程轮数a0a1a2a3a4a5079139355291711379179355292139379175529513931779295541393177955293139317792955表56个数交替排序过程a=8,1,2,6,3,4,7,5a=2,6,3,5,7,4,8,153