C语言中冒泡排序算法的分层次学习

摘要：冒泡排序算法是C语言的重点和难点，不少学习者常常因为冒泡排序算法的难学而对C语言的学习望而却步。该文细致研究冒泡排序算法，细化分层，阶梯式前进，化难为易。

关键词：C语言；算法；排序；冒泡；分层次

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2013）35-7987-03

1 冒泡排序算法

冒泡排序算法是一种基于交换的排序算法。这种算法的基本原理是：将等待排序的元素当作是竖着排列的一系列大小不同的“气泡”，较小的“气泡”较轻，从而要向上浮。冒泡排序算法通过对待排列的“气泡”序列进行若干遍处理，逐步排好所有“气泡”。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确，如果发现两个相邻元素的顺序不正确，即“轻”的元素在下面，就交换位置。易见，一遍处理之后，“最轻”的元素就浮到了最高位置。二遍处理之后，“次轻”的元素就浮到了次高位置。在二遍处理时，由于最高位置上的元素已经是“ 最轻”元素了，所以不必检查最高位置上的元素。一般来说，第n 遍处理时，不必检查第n高位置以上的元素，因为经过前面n- 1遍的处理，它们已正确地排好序了。

2 冒泡排序算法的三个层次

层次一：对数组a按要求进行一遍处理。自底向上（从a[0]到a[9]），依次遍历这个序列，检查相邻的两个元素的顺序是否正确，如果发现相邻的两个元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。

方法过程演示：

完整代码：

#include

main（）

{int a[10]={2，11，1，5，6，12，4，3，9，20}；

int j，temp；

printf（“the origin array is：＼n”）；

for（j=0；j

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

printf（“＼n”）；

//核心代码：

for（j=0；j

if（a[j]

printf（“the sorted array is：＼n”）；

for（j=0；j

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

printf（“＼n”）；

}

程序运行结果是：

小结：数组a[10]={ 2，11，1，5，6，12，4，3，9，20}中的10个元素经过上面的一遍处理后，逐步实现最轻的元素冒到这组数最后的位置，得到数组a的新的排列a[10]={ 11，2，5，6，12，4，3，9，20，1}。

层次二：利用一遍处理的成果，将数组a剩下的待排序的元素{11，2，5，6，12，4，3，9，20}，再次利用“层次一”的方法，对数组a按要求进行二遍处理。自底向上（从a[0]到a[8]），依次遍历这个序列，检查相邻的两个元素的顺序是否正确，如果发现相邻的两个元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。

方法过程演示：

完整代码：

#include

main（）

{int a[10]={ 11，2，5，6，12，4，3，9，20，1}；

int j，temp；

printf（“the origin array is：＼n”）；

for（j=0；j

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

printf（“＼n”）；

for（j=0；j

if（a[j]

printf（“the sorted array is：＼n”）；

for（j=0；j

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

printf（“＼n”）；

}

程序运行结果：

小结：将数组a[10]={ 11，2，5，6，12，4，3，9，20，1}中的10个元素经过“层次一”和“层次二”后得到数组a的新的排列a[10]={11，5，6，12，4，3，9，20，2，1}。可见，这个数组中的次轻数2已经冒到次后的位置（a[8]）。

层次三：达成将数组a[10]中的所有的数由大到小排序，可以重复上面的操作，这就是冒泡排序算法。

完整的方法过程演示：

完整代码：

4 冒泡排序算法的优点

首先，冒泡排序算法的“编程复杂度”很低，理解了冒泡排序原理之后，很容易写出代码。其次，冒泡排序算法具有“稳定性”，所谓“稳定性”是指原序列中相同元素的相对顺序仍然会保持到排序后的序列中。

当然，当需要排序的数据较多且无序时，冒泡排序算法的时间复杂度大，比较次数多，系统开销大。不过，通过改进冒泡排序算法，可以减少比较的次数，降低算法的时间复杂度。

参考文献：

[1] 李秉璋，李红卫，C语言程序设计与训练[M].大连：大连理工大学出版社，2011.