第 24 课：冒泡排序
顾名思义，这个算法的名字由来是最小的元素在不断交换中，像气泡一样慢慢“浮”到数列的顶端。先来了解一下它的概念。
24.1 冒泡排序的概念及步骤
概念
冒泡排序（bubble sort）是一种基础排序算法。
它会重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误，就把它们交换过来。走访数列的工作重复进行，直到再没有元素需要交换，也就是说该数列已经排序完成。
步骤（以从小到大排序为例）
先比较相邻的元素，如果第一个比第二个大，就交换它们两个。
对每一对相邻元素做同样的工作，从开始的第一对到结尾的最后一对，这一步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
每次对越来越少的元素重复上面的步骤，直到没有任何一对数需要比较。
24.2 演示及实现
演示
下面以将数组 [5, 3, 8, 4, 2] 按照从小到大排序为例，详细说明冒泡排序的过程。
- 第一轮排序
a. 比较第 1 个和第 2 个元素（5 和 3），因为 5 > 3，所以交换它们的位置，数组变为 [3, 5, 8, 4, 2]。
b. 比较第 2 个和第 3 个元素（5 和 8），因为 5 < 8，所以位置不变，数组还是 [3, 5, 8, 4, 2]。
c. 比较第 3 个和第 4 个元素（8 和 4），因为 8 > 4，所以交换它们的位置，数组变为 [3, 5, 4, 8, 2]。
d. 比较第 4 个和第 5 个元素（8 和 2），因为 8 > 2，所以交换它们的位置，数组变为 [3, 5, 4, 2, 8]。
经过第一轮排序，最大的元素 8 已经“浮”到了数组的末尾。
- 第二轮排序
a. 比较第 1 个和第 2 个元素（3 和 5），因为 3 < 5，所以位置不变，数组还是 [3, 5, 4, 2, 8]。
b. 比较第 2 个和第 3 个元素（5 和 4），因为 5 > 4，所以交换它们的位置，数组变为 [3, 4, 5, 2, 8]。
c. 比较第 3 个和第 4 个元素（5 和 2），因为 5 > 2，所以交换它们的位置，数组变为 [3, 4, 2, 5, 8]。
经过第二轮排序，第二大的元素 5 也到了它最终的位置。
- 第三轮排序
a. 比较第 1 个和第 2 个元素（3 和 4），因为 3 < 4，所以位置不变，数组还是 [3, 4, 2, 5, 8]。
b. 比较第 2 个和第 3 个元素（4 和 2），因为 4 > 2，所以交换它们的位置，数组变为 [3, 2, 4, 5, 8]。
- 第四轮排序
a. 比较第 1 个和第 2 个元素（3 和 2），因为 3 > 2，所以交换它们的位置，数组变为 [2, 3, 4, 5, 8]。
代码实现
#include <iostream>
using namespace std;
int main()
{
int arr[] = {5, 3, 8, 4, 2};
int n = 5;
// 冒泡排序
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
// 交换 arr[j] 和 arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
cout << "排序后的数组： ";
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
return 0;
}24.3 实例讲解
例 1：第 k 小的数
给定一个长度为 n（1 ≤ n ≤ 10000）的序列，问该序列中第 k（1 ≤ k ≤ n）小的元素是多少。
【输入格式】输入两行。第 1 行输入两个整数 n 和 k。
第 2 行输入 n 个数，表示这个序列。
【输出格式】输出一行，为第 k 小的元素。
【输入样例】
5 3
18 23 4 5 12【输出样例】12
解析
通过冒泡排序对序列进行从小到大排序，排在第几位就是第几小的元素，直接输出这个元素即可。
参考代码
#include <iostream>
using namespace std;
int s[10001];
int main()
{
int n, k;
cin >> n >> k; // n 表示共 n 个数，k 表示输出第 k 个元素
for (int i = 1; i <= n; i++)
cin >> s[i];
for (int i = 1; i <= n - 1; i++)
{
for (int j = 1; j <= n - i; j++)
{
if (s[j] > s[j + 1]) // 从小到大排序
{
int t;
t = s[j];
s[j] = s[j + 1];
s[j + 1] = t;
}
}
}
cout << s[k]; // 数组下标从 1 开始，所以第 k 小的元素即为 s[k]
return 0;
}24.4 冒泡排序优化
在某些序列，比如 [12, 35, 99, 18, 76] 的冒泡排序过程中，我们不难发现，第二轮排序进行完之后，整个序列已经是有序的了，也就是说第二轮排序结束就可以不用进行接下来的比较了。
因此我们可以对刚才的程序进行优化。那么什么时候可以结束排序过程呢？经过观察我们发现，如果某轮排序过程中没有交换发生，那么就说明序列已经有序，无须再次比较了。
优化代码
#include <iostream>
using namespace std;
int main()
{
int n, flag = 1; // flag 标记是否有交换
int arr[200];
cin >> n;
for (int i = 1; i <= n; i++)
cin >> arr[i];
for (int i = 1; i <= n - 1; i++)
{
if (flag == 0) // 没有交换，直接结束排序
break;
flag = 0; // 每轮比较均初始化 flag
for (int j = 1; j <= n - i; j++)
{
if (arr[j] > arr[j + 1])
{
flag = 1; // 有交换发生则标记为 1
int t = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = t;
}
}
}
for (int i = 1; i <= n; i++)
cout << arr[i] << " ";
return 0;
}例 2：枇杷树
蛙蛙在他的果树林里种了两个品种的枇杷树，第一种高度为 2 米，第二种高度为 3 米。
它们在园地中从低到高排成了一排，现在蛙蛙只知道他一共种了 n 棵枇杷树，但不知道每种枇杷树各有多少棵。
但他有一份树高记录表，每种一棵树他就会在表中做记录。由于枇杷树并不是按照从低到高的顺序种植的，所以表中的记录是无序的。他打算把种植的这一排枇杷树的前 m 棵卖掉，请问第 m 棵枇杷树的高度是 2 还是 3？
【输入格式】输入两行。第 1 行是两个由空格隔开的整数 n、m，表示一共有 n 棵枇杷树（n < 10000），求种的第 m 棵枇杷树的高度。
第 2 行是 n 个由空格隔开的整数，h1, h2, …, hn，分别表示一棵树的高度。
【输出格式】输出一行，为种的树中第 m 棵树的高度。
【输入样例】
8 2
2 3 3 2 2 3 3 2【输出样例】2
注：原书此处缺少【输出样例】，根据题目解析与样例数据补全为 2。
解析
根据输入的 n 和 m，对第二行输入的 n 个整数进行排序，从排序后的数组中直接取出第 m 个整数，该整数就是第 m 棵枇杷树的高度。
比如在样例中，排序后第 2 棵枇杷树的高度为 2 米，所以输出为 2。
参考代码
#include <iostream>
using namespace std;
int s[10001];
int main()
{
int n, m, flag = 1;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> s[i];
for (int i = 1; i <= n - 1; i++)
{
if (flag == 0)
break;
flag = 0;
for (int j = 1; j <= n - i; j++)
{
int t;
if (s[j] > s[j + 1])
{
flag = 1;
t = s[j + 1];
s[j + 1] = s[j];
s[j] = t;
}
}
}
cout << s[m];
return 0;
}