[排序篇] 冒泡排序

一、概念

二、冒泡排序

2.1 冒泡降序(从大到小排序)

2.2 冒泡升序(从小到大排序)

三、冒泡排序应用

总结

一、概念

冒泡排序核心思想：每次比较两个相邻的元素，如果它们不符合排序规则（升序或降序）则把它们交换过来。

二、冒泡排序

2.1 冒泡降序(从大到小排序)

冒泡降序：每次比较相邻的两个数，如果后面的数比前面的数大，则交换这两个数的位置。

假设将 12 18 76 35 99 这 5 个数进行从大到小的排序（即，越小的越靠后）。

如上图所示，从左往右逐列看，5 个数总共需要遍历 4 次（即 n - 1 次）；而每列从上往下逐行看，每遍历一次总共需要排序 n - i 次（i 代表遍历的次数）。

1. 首先看第一列：

1.1 第一行：比较第 1 位和第 2 位的大小，发现 12 比 18 要小，因为是降序，所以需要交换这两个数的位置。交换之后这 5 个数的顺序是 18 12 76 35 99；

1.2 第二行：比较第 2 位和第 3 位的大小，发现 12 比 76 要小，因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 18 76 12 35 99；

1.3 第三行：比较第 3 位和第 4 位的大小，发现 12 比 35 要小，因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 18 76 35 12 99；

1.4 第三行：比较第 4 位和第 5 位的大小，发现 12 比 99 要小，因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 18 76 35 99 12；

遍历第一次并经过 4 次排序后，5 个数中最小的一个 12 已经归位到队列的最后一位了（即第 5 位）。

2. 再看第二列：

2.1 第一行：比较第 1 位和第 2 位的大小，发现 18 比 76 要小，因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 76 18 35 99 12；

2.2 第二行：比较第 2 位和第 3 位的大小，发现 18 比 35 要小，因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 76 35 18 99 12；

2.3 第三行：比较第 3 位和第 4 位的大小，发现 18 比 99 要小，因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 76 35 99 18 12；

遍历第二次并经过 3 次排序后，5 个数中倒数第二小的一个 18 已经归位到队列的倒数第二位了（即第 4 位）。

3. 再看第三列：

2.1 第一行：比较第 1 位和第 2 位的大小，发现 76 比 35 要大，则不需要交换这两个数的位置。并且这 5 个数的顺序仍然是 76 35 99 18 12；

2.2 第二行：比较第 2 位和第 3 位的大小，发现 35 比 99 要小，因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 76 99 35 18 12；

遍历第三次并经过 2 次排序后，5 个数中倒数第三小的一个 35 已经归位到队列的倒数第三位了（即第 3 位）。

3. 最后看第四列：

2.1 第一行：比较第 1 位和第 2 位的大小，发现 76 比 99 要小，因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 99 76 35 18 12；

遍历第四次并经过 1 次排序后，5 个数中倒数第四小的一个 76 已经归位到队列的倒数第四位了（即第 2 位）。

最后总结一下：如果有 n 个数进行排序，只需将 n-1 个数归位，也就是说要进行 n-1 次操作。而 “每一次” 都需要从第 1 位开始进行相邻两个数的比较，将较小的一个数放在后面，比较完毕后向后移一位继续比较下面两个相邻数的大小，重复此步骤，直到最后一个尚未归位的数，已经归位的数则无需再进行比较。

冒泡降序例程1(推荐)：

#include <stdio.h>void main()
{int arr[5];int n;int tmp;scanf("%d", &n); //输入一个数n，表示接下来有n个数for (int i = 0; i < n; i++) //循环读入n个数到数组arr中scanf("%d", &arr[i]);//冒泡降序的核心代码for (int i = 1; i <= n - 1; i++) { //n个数排序，只需进行 n-1 次(i从1开始，因此i需要包含 n-1)for (int j = 0; j < n - i; j++) { //i从1开始，则j从第1位(数组0下标)开始与后面一个数比较，直到最后一个尚未归位的数(已归位的数无需再比较，因此只需排序 n-i 次)if (arr[j] < arr[j+1]) { //相邻两个数比较大小并交换tmp = arr[j];arr[j] = arr[j+1];arr[j+1] = tmp;}}}//输出结果for (int i = 0; i < n; i++)printf("%d ", arr[i]);printf("\n");
}

冒泡降序例程2：

#include <stdio.h>void main()
{int arr[5];int n;int tmp;scanf("%d", &n); //输入一个数n，表示接下来有n个数for (int i = 0; i < n; i++) //循环读入n个数到数组arr中scanf("%d", &arr[i]);//冒泡降序的核心代码for (int i = 0; i < n - 1; i++) { //n个数排序，只需进行 n-1 次(i从0开始，因此i不能包含 n-1)for (int j = 1; j < n - i; j++) { //i从0开始，则j从第2位(即数组1下标)开始与前面一个数比较，直到最后一个尚未归位的数(已归位的数无需再比较，因此只需排序 n-i 次)if (arr[j-1] < arr[j]) { //相邻两个数比较大小并交换tmp = arr[j-1];arr[j-1] = arr[j];arr[j] = tmp;}}}//输出结果for (int i = 0; i < n; i++)printf("%d ", arr[i]);printf("\n");
}

冒泡降序例程3：

#include <stdio.h>void main()
{int arr[5];int n;int tmp;scanf("%d", &n); //输入一个数n，表示接下来有n个数for (int i = 0; i < n; i++) //循环读入n个数到数组arr中scanf("%d", &arr[i]);//冒泡降序的核心代码for (int i = 0; i < n - 1; i++) { //n个数排序，只需进行 n-1 次 (i从0开始，因此i不能包含 n-1)for (int j = 0; j < n - i - 1; j++) { //从第1位(数组0下标)开始与后面一个数比较，直到最后一个尚未归位的数(已归位的数无需再比较，然而i和j都是从0开始，因此只需排序 n-i-1 次)if (arr[j] < arr[j+1]) { //相邻两个数比较大小并交换tmp = arr[j];arr[j] = arr[j+1];arr[j+1] = tmp;}}}//输出结果for (int i = 0; i < n; i++)printf("%d ", arr[i]);printf("\n");
}

2.2 冒泡升序(从小到大排序)

冒泡升序：每次比较相邻的两个数，如果后面的数比前面的数小，则交换这两个数的位置。

假设将 99 35 18 76 12 这 5 个数进行从小到大的排序（即，越大的越靠后）。

1. 首先看第一列：

1.1 第一行：比较第 1 位和第 2 位的大小，发现 99 比 35 要大，因为是升序，所以需要交换这两个数的位置。交换之后这 5 个数的顺序是 35 99 18 76 12；

1.2 第二行：比较第 2 位和第 3 位的大小，发现 99 比 18 要大，因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 35 18 99 76 12；

1.3 第三行：比较第 3 位和第 4 位的大小，发现 99 比 76 要大，因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 35 18 76 99 12；

1.4 第三行：比较第 4 位和第 5 位的大小，发现 99 比 12 要大，因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 35 18 76 12 99；

遍历第一次并经过 4 次排序后，5 个数中最大的一个 99 已经归位到队列的最后一位了（即第 5 位）。

2. 再看第二列：

2.1 第一行：比较第 1 位和第 2 位的大小，发现 35 比 18 要大，因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 18 35 76 12 99；

2.2 第二行：比较第 2 位和第 3 位的大小，发现 35 比 76 要小，则不需要交换这两个数的位置。并且这 5 个数的顺序仍然是 18 35 76 12 99；

2.3 第三行：比较第 3 位和第 4 位的大小，发现 76 比 12 要大，因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 18 35 12 76 99；

遍历第二次并经过 3 次排序后，5 个数中第二大的一个 76 已经归位到队列的倒数第二位了（即第 4 位）。

3. 再看第三列：

2.1 第一行：比较第 1 位和第 2 位的大小，发现 18 比 35 要小，则不需要交换这两个数的位置。并且这 5 个数的顺序仍然是 18 35 12 76 99；

2.2 第二行：比较第 2 位和第 3 位的大小，发现 35 比 12 要大，因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 18 12 35 76 99；

遍历第三次并经过 2 次排序后，5 个数中第三大的一个 35 已经归位到队列的倒数第三位了（即第 3 位）。

3. 最后看第四列：

2.1 第一行：比较第 1 位和第 2 位的大小，发现 18 比 12 要大，因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 12 18 35 76 99；

遍历第四次并经过 1 次排序后，5 个数中第四大的一个 18 已经归位到队列的倒数第四位了（即第 2 位）。

最后总结一下：如果有 n 个数进行排序，只需将 n-1 个数归位，也就是说要进行 n-1 次操作。而 “每一次” 都需要从第 1 位开始进行相邻两个数的比较，将较大的一个数放在后面，比较完毕后向后移一位继续比较下面两个相邻数的大小，重复此步骤，直到最后一个尚未归位的数，已经归位的数则无需再进行比较。

冒泡升序例程1(推荐)：

#include <stdio.h>void main()
{int arr[5];int n;int tmp;scanf("%d", &n); //输入一个数n，表示接下来有n个数for (int i = 0; i < n; i++) //循环读入n个数到数组arr中scanf("%d", &arr[i]);//冒泡降序的核心代码for (int i = 1; i <= n - 1; i++)) { //n个数排序，只需进行 n-1 次(i从1开始，因此i需要包含 n-1)for (int j = 0; j < n - i; j++) { //i从1开始，则j从第1位(数组0下标)开始与后面一个数比较，直到最后一个尚未归位的数(已归位的数无需再比较，因此只需排序 n-i 次)if (arr[j] > arr[j+1]) { //相邻两个数比较大小并交换tmp = arr[j];arr[j] = arr[j+1];arr[j+1] = tmp;}}}//输出结果for (int i = 0; i < n; i++)printf("%d ", arr[i]);printf("\n");
}

冒泡升序例程2：

#include <stdio.h>void main()
{int arr[5];int n;int tmp;scanf("%d", &n); //输入一个数n，表示接下来有n个数for (int i = 0; i < n; i++) //循环读入n个数到数组arr中scanf("%d", &arr[i]);//冒泡降序的核心代码for (int i = 0; i < n - 1; i++) { //n个数排序，只需进行 n-1 次(i从0开始，因此i不能包含 n-1)for (int j = 1; j < n - i; j++) { //i从0开始，则j从第2位(即数组1下标)开始与前面一个数比较，直到最后一个尚未归位的数(已归位的数无需再比较，因此只需排序 n-i 次)if (arr[j-1] > arr[j]) { //相邻两个数比较大小并交换tmp = arr[j-1];arr[j-1] = arr[j];arr[j] = tmp;}}}//输出结果for (int i = 0; i < n; i++)printf("%d ", arr[i]);printf("\n");
}

冒泡升序例程3：

#include <stdio.h>void main()
{int arr[5];int n;int tmp;scanf("%d", &n); //输入一个数n，表示接下来有n个数for (int i = 0; i < n; i++) //循环读入n个数到数组arr中scanf("%d", &arr[i]);//冒泡降序的核心代码for (int i = 0; i < n - 1; i++) { //n个数排序，只需进行 n-1 次 (i从0开始，因此i不能包含 n-1)for (int j = 0; j < n - i - 1; j++) { //从第1位(数组0下标)开始与后面一个数比较，直到最后一个尚未归位的数(已归位的数无需再比较，然而i和j都是从0开始，因此只需排序 n-i-1 次)if (arr[j] > arr[j+1]) { //相邻两个数比较大小并交换tmp = arr[j];arr[j] = arr[j+1];arr[j+1] = tmp;}}}//输出结果for (int i = 0; i < n; i++)printf("%d ", arr[i]);printf("\n");
}

三、冒泡排序应用

假设一个班有 5 个学生，需要将这 5 个学生期末考试的分数，从高到低排序，并且输出对应的学生姓名和性别。大家可以思考一下，该如何实现？

根据 2.1 冒泡降序原理，在此，我们只需要声明一个结构体，其成员包含学生的姓名、性别和分数（假设满分为 100，并分数只有整数）。下面是实际的例子。

#include <stdio.h>struct student {char name[24];char sex[8];int score;
};void main()
{struct student stu[5];struct student tmp;int n;scanf("%d", &n); //输入班级总人数for (int i = 0; i < n; i++) //循环读入学生总数到数组stu中scanf("%s %s %d", stu[i].name, stu[i].sex, &stu[i].score);//开始对学生进行分数排序for (int i = 1; i <= n - 1; i++) {for (int j = 0; j < n - i; j++) {if (stu[j].score < stu[j+1].score) { //比较相邻的两个数，分数高的排前面tmp = stu[j];stu[j] = stu[j+1];stu[j+1] = tmp;}}}//输出结果for (int i = 0; i < n; i++)printf("%s %s %d", stu[i].name, stu[i].sex, &stu[i].score);printf("\n");
}

可以输入以下数据进行验证：

5

李文男 80
韩飞男 50
晓晓女 86
胡峰男 78
陈肖女 66

运行结果是：

晓晓女 86

李文男 80
胡峰男 78
陈肖女 66
韩飞男 50

总结

1. 冒泡降序：每次比较相邻的两个数，如果后面的数比前面的数大，则交换这两个数的位置；

2. 冒泡升序：每次比较相邻的两个数，如果后面的数比前面的数小，则交换这两个数的位置；

3. 从例程代码来看，可知冒泡排序有很多种方法，但是万变不离其宗，都是围绕 “如果有 n 个数进行排序，则需遍历 n-1 次，而 “每一次” 需要排序 n-i 次，并且都是从第 1 位开始进行相邻两个数的比较，将较小或较大的一个数放在后面，如此重复，直到最后一个尚未归位的数” 展开。

4. “冒泡降序” 与 “冒泡升序” 例程代码的唯一差异是：相邻的两个数较小或较大的放在后面。例如，if (arr[j] < arr[j+1]) 或 if (arr[j] > arr[j+1])；

5. 冒泡排序的核心部分是双重嵌套循环。不难看出冒泡排序的时间复杂度是 O( $N^{2}$ )。这是一个非常高的时间复杂度。正如 Donald E. Knuth 所说：“冒泡排序除了它迷人的名字和导致了某些有趣的理论问题这一事实之外，似乎没有什么值得推荐的。”