冒泡排序及其改进算法的教学设计与实现

曹春梅　宋洁

摘 要：在C语言程序设计中，排序算法是使用频率最高的算法之一，而冒泡排序是其中一种典型且相对简单的方法，学习它是为后面的选择排序作铺垫。文章在最初的冒泡排序算法上改进了两次，使算法达到一个更好的效果。通过冒泡排序及其改进算法的学习，可以提高学生的程序设计能力，为今后在算法与程序设计方面的进一步研究和学习打下基础。

关键词：C语言；排序算法；冒泡排序；改进算法；程序设计能力

1 冒泡排序算法

1.1 导入

首先可以通过生活中常见的例子来引出问题。由图1提出问题：如何将这6支长短不一的铅笔进行由短到长的排序？

经过讨论，发现排序方法有很多种，本文主要介绍其中一种—冒泡排序法[1-3]。

为了对冒泡排序有直观的了解，我们通过Flash动画[4-5]演示排序过程：在每一趟的排序中，将铅笔两两比较，较长的铅笔移至后面。通过第一趟排序，最长的铅笔移至最后面。依次类推，第二趟排序后，第二长的铅笔移至倒数第二的位置；第三趟排序后，第三长的铅笔移至倒数第三的位置；第四趟排序后，第四长的铅笔移至倒数第四的位置；第五趟排序后，第五长的铅笔移至倒数第五的位置，剩下的那支铅笔必然是最短的，而且排在第一的位置。

1.2 典型例子分析

为了更好地理解算法，我们通过一个典型例子来分析：用冒泡排序的方法将一组无序数据72，34，61，93，45，9排成从小到大的顺序。

为了方便分析，我们把所给的数据先用一个表格列出来，如表1所示。

按照冒泡排序算法，对这些数据进行由小到大的排序：在每一趟排序中，将数字两两比较，若较大数在前，较小数在后，则将两个数交换位置，否则，两数位置不变。经过第一趟排序后，最大数93沉到最底。依次类推，第二趟排序后，第二大数72沉到倒数第二个位置；第三趟排序后，第三大数61沉到倒数第三个位置；第四趟排序后，第四大数45沉到倒数第四个位置；第五趟排序后，第五大数34沉到倒数第5个位置，最小数9就理所当然地在第一个位置。

1.3 算法原理

由典型例子的分析可知，在每趟排序过程中，所有数字都要进行两两比较，找出相应的最大值，并依次排好顺序。

由此，冒泡排序的原理是：对原始数据按从前往后的方向进行多次扫描，每次扫描称为一趟。当发现相邻两个数据的次序与排序要求的大小次序不符合时，即将这两个数据进行互换。这样，较小的数据就会逐个向前或向后移动。

1.4 算法设计

1.4.1 数据的输入

定义一个一维数组a，存储72，34，61，93，45和9。并且定义两个表示循环中的趟数、次数的变量，以及一个用来暂时存储数值的变量。

1.4.2 数据的输出

通过for语句for（i=0； i<6； i++ ），让循环执行6次，输出6个数据。

1.4.3 每一趟比较程序设计

通过for语句for（i=0； i<5； i++ ），让循环执行5次，也就是让数组中的数据两两比较，若前一个数据大于后一个数据，就会发生交换。

1.4.4 趟数控制的程序设计

在内层for语句的外侧加上一层for语句for（j=0； j<5； j++），让循环执行5次，也就是说比较5趟。

根据这4个步骤，可得冒泡排序的代码为：

void main（）

{

int a[6]={72，34，61，93，45，9}；

int t， i ， j ；

for（j=0； j<5； j++）

{

for（i=0； i<5； i++）

{

if（a[i]>a[i+1]）

{ t=a[i]； a[i]=a[i+1]； a[i+1]=t；}

}

}

for（i=0； i<6； i++）

print f（“%d”， a[i]）；

}

1.5 思考题

从典型例子分析和算法设计可以看出，每一趟的比较都是a[0]和a[1]比较，a[1]和a[2]比较，a[2]和a[3]比较，a[3]和a[4]比较，a[4]和a[5]比较，过程比较繁琐，而且效率低下，能否对算法进行优化呢？

1.6 小结

方法总结：n个数排序，從前往后，比较相邻的两个数，前大后小，则交换，否则，不交换；该过程需要重复（n-1）趟。

算法总结：循环语句两两比较；条件语句判别大小；赋值语句用来交换。

2 冒泡排序之改进算法

2.1 回顾旧知

本文之前的章节中讲述了最初的冒泡排序算法[6-8]。其中，每趟排序中数据比较的次数是相同的，现在的重点是将每趟排序中的比较次数优化，使算法效率有所提高。

2.2 引入新知

在上一章的典型例子分析中，首先观察第一趟与第二趟排序结束后的数据，可以看到第一趟排序后最大值93排到最后，在第二趟排序中，其实无需将其他数值与最后一个值比较，这样比较次数就可以少一次。在第三趟排序中，其实无需将其他数值与最后一个值、倒数第二个值比较，这样比较次数就可以少两次。后面的依次类推。最后可以得到一个结论，对n个数排序，在第j趟排序中只需进行（n-j）次两两比较。

2.3 动画演示

为了更好地理解改进算法，我们通过Flash动画演示排序过程。

第一趟排序和未改进的算法一样，两两比较，排序完成后93位于最后位置。根据改进算法的描述，第二趟排序时其他柱体无需与已排在最后的柱体比较，所以会少一次比较，只需进行4次比较。依次类推，第三趟排序需进行3次比较；第四趟排序需进行2次比较；第五趟排序进行1次比较即可。

这个动画可以进一步验证这次改进算法的正确性。对n个数排序，在第j趟排序中只需进行（n-j）次两两比较，可以适当提高算法效率。

2.4 改进算法

在改进算法中，数据输入、数据输出、排序趟数和原算法不变，所以不再赘述。在改进算法中有所改变的是每一趟比较程序设计环节：通过for语句for（i=0； i<5-j； i++）实现各次比较，每次的比较都是前后数据两两比较，若前一个数据大于后一个数据，就会发生交换，否则，不交换。

根据改进算法得到的代码为：

void main（）

{

int a[6]={72，34，61，93，45，9}；

int t， i ， j ；

for（j=0；j<5；j++）

{

for（i=0； i<5-j； i++）

{

if（a[i]>a[i+1]）

{ t=a[i]； a[i]=a[i+1]； a[i+1]=t；}

}

}

for（i=0；i<6；i++）

printf（“%d”， a[i]）；

}

2.5 思考题

在这次的改进算法中，对每趟排序中的比较次数进行了优化，使效率有所提高。现在我们思考一个问题，如果n个元素排序，不到（n-1）趟时，已经有序，还需要进行后续的排序吗？

2.6 小结

使用改进的冒泡排序算法对n个数进行由小到大的排序，需要进行（n-1）趟排序，在第j趟排序中，只需进行（n-j）次两两比较。

3 冒泡排序之再改进算法

3.1 回顾旧知

在冒泡排序的改进算法中，我们将内层循环中的i<5改为i<（5-j），使其当前一轮比较确定一个最大的数据后，下一轮该数就不再参与比较。现在考虑的是对于不同的数值排序，排序趟数能否不一样，是不是可以在这方面进行优化。

3.2 引入新知

比如现在有n个元素需要进行排序，但是不到（n-1）趟时，已经有序了，我们就可以提前终止比较。这次改进算法的关键是要加入flag变量作为程序的交换标志。

3.3 改进算法

为了更好地描述改进算法，我们举例说明：用冒泡排序的方法将一组无序数据19，25，10，45，36排成从小到大的顺序。

外层循环和内层循环的整体设计和之前改进的冒泡排序算法一致，不同的是需要在外层循环的内部，且位于内层循环的外部加入一个flag标志，让其初始值为0。在内层循环中，若在某次比较中有数据交换了位置，就将flag的值改为1；若没交换，flag值就不变。一趟排序之后，判断flag是否为0，如果为0，意味着所有数据已经有序，后面无需再交换，就可以跳出循环，比较终止。否则，继续排序。

根据这进一步的改进，得到的代码为：

void main（）

{

int a[5]={19，25，10，45，36}；

int t， i ， j ；

for（j=0； j<4； j++）

{

flag=0；

for（i=0；i<4-j；i++）

{

if（a[i]>a[i+1]）

{

flag=1；

t=a[i]； a[i]=a[i+1]； a[i+1]=t；

}

}

if（flag==0） break；

}

for（i=0； i<5；i++）

printf（“%d”， a[i]）；

}

3.4 思考题

之前介绍的算法设计都是通过寻找最大值的方法来实现的，我們可以思考这样一个问题，如何采用每一轮比较寻找最小值的方法实现冒泡排序的算法设计。

3.5 小结

使用再改进的冒泡排序算法对n个数进行由小到大的排序，在其中加入flag标志，并设置一个初值，若在某趟排序中flag值未发生改变，表明数据已有序，无需进行后续的排序。

4 结语

本文介绍了冒泡排序及其两种改进算法的教学设计与实现。由最初的排序算法到后来的两种改进，采取循序渐进的方法，这样更有助于学生的理解，能让他们更好地掌握。

[参考文献]

[1]李坤，邓波.冒泡排序算法的分析与改进[J].科技信息，2010（22）：216.

[2]程妮.C语言中冒泡排序算法的教学设计与分析[J].现代计算机（专业版），2016（10）：59-63.

[3]刘培元.C语言中冒泡排序算法的分层次学习[J].电脑知识与技术，2013（35）：7987-7989.

[4]刘卉媚. Flash动画制作技巧[J].才智，2012（23）：199.

[5]苏也惠. FLASH动画在新媒体中的应用研究[J].艺术科技，2015（9）：295.

[6]RAMIN E，ARMIN E，TAYEBEH M.A sort implementation comparing with bubble sort and selection sort[C].Shanghai：2011 3rd International Conference on Computer Research and Development，2011：380-381.

[7]HADI S.Multimedia based instructional development：Bubble sort visualization[C].Beijing：2015 6th IEEE International Conference on Software Engineering and Service Science（ICSESS），2015：791-794.

[8]YUNXIA R，SHIYING W. Diagnosability of bubble-sort graph networks under the comparison diagnosis model[C].Jabalpur：2015 International Conference on Computational Intelligence and Communication Networks（CICN），2015：823-826.