-
可编辑
18.2.2
冒泡排序
“冒泡”是什么意思？湖底有时会冒出一个气泡，气泡刚在湖底时，是很小的，在向上浮
的
过程中，才一点地慢慢变大。学过高中的物理的人，应该不难解释这一现象。冒泡排序
的过程
有点类似这个过程，每前进一步，值就大一点。
排序当然有两个方向，
一种是从小排到大，
一种是从大排到小。
大多数教科书里都讲第一种，
我们也如此。
这样一来，冒泡排序法就改为“沉泡法”了，较大值一点点跑到数组中的末尾。
一般教科书里也会说，冒泡排序法是人们最熟悉，及最直观的排序法，我可不这样认为。或<
/p>
许老外在生活中用的是这种最笨的排序法？我猜想，
大家在生活中
99%
使用后面要讲的
“选择”
排序法。
冒泡排序是这么一个过程
(
从小到大
):
1
、
比较相邻的两个元素，
如果后面的比前面
小，
就对调二者。
反复比较，
到最后两
个元素。
结果，最大值就跑到了最末位置。
2
、反复第一步，直到所有较大值都
跑到靠后的位置。
看一眼例子：
2
，
5
，
1
，
4
，
3
第一遍：
·比较第一对相邻元素：
2
，
5
，发现后面的
5
并不比
2
小，
所以不做处理。
序列保持不变：
2
，
5<
/p>
，
1
，
4
，
3
精品文档，欢迎下载
可编辑
·继续比较后两对元素：
5
，
1
，发现后面
的
1
比前面的
5
小，所以对调二者。现在，序列变
为：
2
，
1
，
5
，
4
，
3
·继续比较后两对元素：
5
，
4
……对调，于是：
2
，
1
，
4
，<
/p>
5
，
3
·继续比较后两对元素：
5
，
3
……对调，于是：
2
，<
/p>
1
，
4
，
3
，
5
<-----
OK,
现在最大值
5
跑
到最尾处了。
大泡泡“
5
”浮出来了，但前面的
2,1,4,3,
还是没有排好，没事，再来一遍，不过，由于最
后一个元素肯定是最大值了，所以我们这回只排到倒数第二个即可。
第二遍：
·比较第一对相邻元素：
2
，
1
，发现
1
比
2
小，所以对调：
1,2
,4,3,5
·继续比较后两对元素：
2
，
4
，不用处理，因为后面的数比较大。序列还
是：
1,2,4,3,5
·继续
4
，
3
，对调：
1,2,
3,4
,5
。
前面说，
5
不用再参加比较了。现在
的序列是
1
，
2
，
3
，
4
，
5
。接下来，我们再来一遍：
第三遍：
·比较第一对相邻元素：
1
，
2
：不用对调。
……等等……
有人说，现在已经是
1
，
2
，
3
，
4
，
5
了，完全是排好序了啊，何必再来进行呢？我
们确实是
看出前面
1
，
2
，
3
也井然有序了，
但对于程序来说，
它
只能明确地知道自己已经
排好了两个数
：
4
，
< br>5
，并不知道的
1
，
2
，
3
凑巧也排好了。所
以它必须再排两次，直到确认把
3
和
2
都已推到
合适的位置上。最后剩一个数是
1
，因为只有一个数，没得比，所以这才宣告排序结束。
那么到底要排几遍？看一看前面的“第一遍”、“第二遍”的过程你可发现，每进行一遍，<
/p>
可以明确地将一个当前的最大值推到末尾，
所以如果排
Count
个数，
则应排
Count
遍。
当然，
最后一遍是空走，因为仅剩一个元素
，没得比较。
精品文档，欢迎下载
可编辑
下面就动手写冒泡排序法的函
数。
写成函数是因为我们希望这个排序法可处理任意个元素的
数
组。
//
冒泡排序
(
从小到大
)
：
//num:
要接受排序的数组
//count :
该数组的元素个数
void bubble(int num[],int count)
{
int tmp;
//
要排
Count
个数，则应排
Count
遍：
for (int i = 0; i < count; i++)
{
for(int j = 0; j <
count - i -
1
; j++)
{
//
比较相邻的两个数：
if(num[j+1] <
num[j])
{
//
对调两个数，需要有
第三者
参以
tmp = num[j+1];
num[j+1] = num[j];
num[j] = tmp;
}
}
}
}
注意在内层循环中
j
的结束值是
count
-
i
-
1
。
要理解
这段代码，
明白为什么结束在
count
-
i
-1
？如果你忘了如何在
CB
进行代码调试，如果设置断点，如何单
步运行，如何观察变量的
精品文档，欢迎下载
可编辑
值，那么你需要“严重”复习
前面有关“调试”的章节；如果你一直是高度着每一章的程序到
现在，那么你可以继续下
面的内容。
精品文档，欢迎下载
可编辑
排序函数写出一个了，如何调试这个函数？在
CB
里新建一空白控制台程序，然后在主函数
里，让我
们写一些代码来调用这个函数，并且观察排序结果。
#include
……
void bubble(int num[],int count)
{
……
}
int main() //
我实在
有些懒得写
main
里两个参数，反正它们暂时对我们都没有用
，
//
反正
CB
会为你自动生成，
所以从此刻起，
我不写了
< br>,
除非有必要。
{
int values[] =
{2,5,1,4,3};
int count =
sizeof(values[]) / sizeof(values[0]);
bubble(value,sizeof);
}
你要做的工作是单步跟踪上面的代码，
看看整个流程是不是像我前面
不厌其烦的写的
“第一
遍第二遍第三遍”所描述的。
完成上面的工作了吗？全部过程下来，只花
< br>20
分钟应该算是速度快或者不认真的了（天知
道你是哪
一种？天知道你到底是不是没有完成就来骗我？）。现在让这个程序有点输出。我们
加一
个小小的函数：
//
输出数组的元素值
精品文档，欢迎下载
可编辑
//num
:
待输出的数组
//count:
元素个数
void printArray(int
num[],int count)
{
for(int i = 0;
i < count; i++)
{
count <<
num[i] <<
}
cout << endl;
}
把这个函数加到
main()
函数头之前，然后我们用它来输出：
int main() //
我实在有些懒得写
main
里两个参数，反正它们暂时对我们都没有用，
//
反正
CB
会为你自动生成，
所以从此刻起，
我不写了
,
除非有必要。
{
int values[] = {2,5,1,4,3};
int count = sizeof(values[]) / sizeof(values[0]);
cout <<
排序之前：
printArray(values,count);
//
冒泡排序：
bubble(value,sizeof);
cout <<
排序之后
:
<< endl;
printArray(values,count);
system(
精品文档，欢迎下载
可编辑
}
后面要
讲的其它排序法也将用这个
printArray()
来作输出
。
冒泡排序是效率最差劲的方法（速度慢），不过若论起不另外
占用内存，则它当属第一。在
交换元素中使用了一个临时变量（第三者），还有两个循环
因子
i
和
j
，
这些都属于必须品，
其它的它一个变量也没多占。
我们现在讲讲如何避免数据其实已经排好，程序仍然空转的的局面。
首先要肯定一点，至少一遍的空转是不可避免的，这包括让人
来排，因为你要发现结果已是
1
，
2<
/p>
，
3
，
4
，
5
了，
你也是用眼
睛从头到尾抄了一遍
（如果你视力不好，
说不定还要扫两遍呢）
。
接下来
一点，我们来看看除了第一遍空转，后面的是否可以避免。冒泡排序法的空转意味着
什么
？因为算法是拿相邻的两个比较，
一发现次序不合
“从小到大”
的目的
（小的在大的后头）
，
就进行对调。
所以如果这个对调一次也没有进行，
那就说明后面的元素必然是已经完全有序了，
可以放心地结束。
让我们来加个变量，
用于标志刚刚完成的这一遍是否空转，
如果是空转，
就让代码跳出循环。
//
冒泡排序
(
从
小到大，且加了空转判断
)
：
void bubble(int num[],int
count)
{
int tmp;
bool swapped;
//
有交换吗？
//
要
排
Count
个数，则应排
Count
遍：
for (int i =
0; i < count; i++)
{
精品文档，欢迎下载
-
-
-
-
-
-
-
-
-
上一篇：往年湖北特岗教师招聘考试综合知识真题
下一篇：void详解