排序算法（冒泡法）

排序算法（冒泡法）

背景

  • 循环输入一列数，并找出最大值

这是我写的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>

int find_max(int);

int main() {
	int a[4];
	for (int i = 0;i <= 4;i++) {
		printf("please input: \n");
		scanf_s("%d", &a[i]);
	}
	int max = find_max(a);
	printf("The max is %d", max);
	return 0;
}

int find_max(int a[]) {
	int max = a[0];
	for (int i = 1;i <= 4;i++) {
		if (a[i] > max) {
			max = a[i];
		}
	}
	return max;
}

运行，代码报错

问了一下哈基米：

错误一：函数声明与定义不一致

  • 你的代码：在 main 函数上面，你写的是 int find_max(int);。这意味着告诉编译器这个函数只接收一个整数。
  • 实际情况：在 main 函数下面，你定义的却是 int find_max(int a[])，这接收的是一个数组。
  • 后果：编译器会报错，因为它搞不清到底应该传什么参数。
  • 修改：将开头的声明改为 int find_max(int a[]); 或者 int find_max(int*);。

错误二：数组越界

  • 在定义a[4]时，这里的4表面数组一共有4个元素（实际上我想定义5个元素）
  • 而在后面的 a[i] (i=4) 中，会尝试访问第五个元素
  • 修改：在定义时改成a[5]

修改后：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>

int find_max(int*);

int main() {
	int a[5];
	for (int i = 0;i <= 4;i++) {
		printf("please input: \n");
		scanf_s("%d", &a[i]);
	}
	int max = find_max(a);
	printf("The max is %d", max);
	return 0;
}

int find_max(int a[]) {
	int max = a[0];
	for (int i = 1;i <= 4;i++) {
		if (a[i] > max) {
			max = a[i];
		}
	}
	return max;
}

冒泡法

  • 把你身边的兄弟比一下，如果你比他高，你俩就换位置，你站到他后面去

这是我第一次写这个算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>

void rank(int*,int);
void present(int*);

int main() {
	int a[] = { 78,89,69,98,50 };
	for (int i = 5;i >= 1;i--) {
		rank(a,i-1);
	}
	present(a);
	return 0;
}

//将找到的最小的数字依次往左排
void rank(int a[], int i) {
	int temp;
	for (;i >= 1;i--) {
		if (a[i - 1] > a[i]) {
			temp = a[i - 1];
			a[i - 1] = a[i];
			a[i] = temp;
		}
	}
}

//打印出更新后的数组
void present(int a[]) {
	for (int i = 0;i <= 4;i++) {
		printf("%d ", a[i]);
	}
}

问了一下哈基米，可知道我的代码有些可以改进的地方：

  • 结构上不合适

    通常来说冒泡排序的双循环一般会写在一个函数中，我把外层循环放在 main 里、内层循环放在 rank 里会让代码逻辑变得支离破碎，阅读起来比较累

  • 效率上的小浪费

    你的策略是把最小的数冒泡到最左边（下标0）。那么第一轮结束后，a[0] 已经是最小的了，第二轮就不需要再检查 a[0] 了。但是在你的 rank 函数中，循环条件总是 i >= 1，这意味着每一轮都会去检查 a[0] 和 a[1]，这是多余的比较。

    。。。。。等等，这傻逼Gemini叽里咕噜说啥呢！

我在分析这个“效率上的小浪费‘’，并想找出我的不足时，突然发现我代码并不是效率低，而是写了一个几把！

因为我rank函数中的循环次数一直在减少：

第一次检查a[0],a[1],a[2],a[3],a[4]
第二次检查a[0],a[1],a[2],a[3],a[4]
第三次检查a[0],a[1],a[2],a[3],a[4]
第四次检查a[0],a[1],a[2],a[3],a[4]
第五次检查a[0],a[1],a[2],a[3],a[4]

每一次检查的时候只会找出上述粗体元素的最小值，并往左排

然后缩小范围，然而就在这个缩小范围的时候，被忽略的非粗体元素并没有保证是最大值且按从小到大的顺序

我意识到我能得到正确的排序，好像全是因为巧合！

于是我试了一下，如果我把需要排序的数列改成78,89,69,68,50，最后会得到：50 69 78 89 68（68>89?）

妈的，于是我去质问了一下哈基米：

真的非常抱歉！你说得对，我是完全看走眼了！ 😓

我也要给你点个大大的赞，作为刚学数组的新手，你能敏锐地发现这个逻辑漏洞并举出反例，这说明你对代码运行逻辑的直觉非常好，这是很多初学者（甚至包括刚才那个大意的我）容易忽略的细节。

你说得非常对，之前的代码能跑通确实是巧合。

你的代码到底错在哪？（致命逻辑漏洞）

让我们用你提供的这组数字 78, 89, 69, 68, 50 来复盘一下，看看 68 是怎么“含冤被遗忘”在角落的。

你的代码核心逻辑是：

  1. **内层 rank**：把范围内最小的数“浮”到最左边。
  2. 外层循环：rank(a, 4) -> rank(a, 3) -> rank(a, 2) … 范围越来越小。

案发现场还原：

第一轮 rank(a, 4)： 也就是处理下标 0~4。

  • 程序一路比较交换，把最小的 50 成功送到了最左边 a[0]。
  • 但是！ 注意中间发生的一件事：
    • 当比较 69 和 68 时，没动。
    • 当比较 68 和 50 时（在数组末尾），68 被换到了 50 的位置（也就是 a[4]，最右边）。
    • 此时数组大约是：50, 78, 89, 69, 68（大概样子）。
  • 关键点：68 现在处于最后一位 (下标4)。

第二轮 rank(a, 3)： 灾难发生了！

  • 你的外层循环把参数传成了 3。
  • rank 函数里的循环是 for (; i >= 1; i--)，此时 i 从 3 开始。
  • 这意味着：这一轮只检查下标 0, 1, 2, 3。
  • 下标 4 里的那个 68，直接被无视了！
  • 虽然 68 比 89（假设在下标3）要小，但程序根本不看它。

之后的每一轮，检查范围都在缩小（下标2、下标1…），那个躲在最右边角落（下标4）的 68 再也没有机会被检查，所以它就永远留在了最后面。

为什么之前的代码跑对了？

因为之前那组数 {78, 89, 69, 98, 50}，原本就在最右边的 50 是最小的，它第一轮就被送走了。而第二大的数 69 恰好不在最后一位，没被“卡住”。所以那是运气好。

可以的，态度还行。

在发现问题的这个过程中，我还是收获了很多，即在得到AI的修改意见后（对于效率低），没有仅仅看AI修改后的代码，而是还去复盘自己的代码：

我不封装了函数present(int a[])用于打印排序后的a[]吗？

正好我可以将这个函数调用放在任意一个位置，以测试我的循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>

void rank(int*,int);
void present(int*);

int main() {
	int a[] = { 78,89,69,68,50 };//98
	for (int i = 5;i >= 1;i--) {
		printf("\n第%d次排序", 6 - i);present(a);
		rank(a,i-1);
	}
	printf("\n得到最后的结果：");
	present(a);
	return 0;
}

//将找到的最小的数字依次往左排
void rank(int a[], int i) {
	int temp;
	for (;i >= 1;i--) {
		if (a[i - 1] > a[i]) {
			temp = a[i - 1];
			a[i - 1] = a[i];
			a[i] = temp;
		}
		present(a);
	}
}

//打印出更新后的数组
void present(int a[]) {
	printf("\n");
	for (int i = 0;i <= 4;i++) {
		printf("%d ", a[i]);
	}
}

运行，得到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
第1次排序
78 89 69 68 50
78 89 69 50 68
78 89 50 69 68
78 50 89 69 68
50 78 89 69 68
第2次排序
50 78 89 69 68
50 78 69 89 68
50 69 78 89 68
50 69 78 89 68
第3次排序
50 69 78 89 68
50 69 78 89 68
50 69 78 89 68
第4次排序
50 69 78 89 68
50 69 78 89 68
第5次排序
50 69 78 89 68
得到最后的结果：
50 69 78 89 68

就这样，发现了我的循环次数并没有像哈基米说的那样不变，这才有了后来的事

再来看：我将打印这个语句封装，其实是没事找事想试试，结果反而让我有了用于测试的工具

真可谓是：有心栽花花不开，无心插柳柳成荫

标准冒泡法

后来我重新写了一个标准的冒泡法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>

void bubble_sort(int*, int);

int main() {
	int a[5] = { 78, 89, 69, 98, 50 };
	bubble_sort(a, 5);
	for (int i = 0;i < 5;i++) {
		printf("%d ", a[i]);
	}
}

void bubble_sort(int a[], int n) {
	int temp;
	//只需要跑n-1=4轮
	for (int i = 1;i <= n - 1;i++) {
		//第i轮需要交换n-i次
		for (int j = 0;j <= n - i - 1;j++) {
			if (a[j] > a[j + 1]) {
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
	}
}

基于出现的问题，修改了一下：

  1. 将冒泡法的双循环一起放到bubble_sort函数中

  2. 修改了一下逻辑，每次将最大的往右边挪（冒泡）

    此外，每次从第0个元素开始检测，即实现每次循环交换的次数越来越少，又保证往右排的元素是检测的元素的最大值，且比已经排到右侧的元素小

这样才是一个标标准准的冒泡法

真享受写代码，改代码的过程啊！

排序算法（冒泡法）
http://example.com/2025/11/29/排序算法（冒泡法）/
作者
王柏森
发布于
2025年11月29日
许可协议