排序算法（选择法）

排序算法（选择法）

我瞎写的代码：

上课老师讲选择法的时候我睡着了（实在是困）

现在我利用老师讲个课件中的大致逻辑自己尝试写了一份：

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
37
#include <stdio.h>

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

int main() {
	int a[7] = { 13,38,65,97,76,49,27 };
	selection_sort(a, 7);
	//printf("\n最后的结果");
	present(a, 7);
}

void selection_sort(int a[], int n) {
	//只需要循环n-1=6轮
	for (int i = 0;i <= n - 2;i++) {
		int temp;
		//printf("\n第%d循环", i + 1);
		//每轮循环找出剩下元素的最小值，并放到第i个位置
		for (int j = i;j <= n - 2;j++) {
			if (a[j + 1] < a[i]) {
				//将暂时找到的最小值与a[i]交换
				temp = a[j + 1];
				a[j + 1] = a[i];
				a[i] = temp;
			}
			//present(a, 7);
		}
		//printf("\n第%d循环的结果：", i + 1);present(a, 7);
	}
}

void present(int a[], int n) {
	printf("\n");
	for (int i = 0;i <= n - 1;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
23
24
25
26
27
28
29
30
#include <stdio.h>

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

int main() {
	int a[7] = { 13,38,65,97,76,49,27 };
	selection_sort(a, 7);
	present(a, 7);
}

void selection_sort(int a[], int n) {
	for (int i = 0;i <= n - 2;i++) {
		int temp;
		for (int j = i;j <= n - 2;j++) {
			if (a[j + 1] < a[i]) {
				temp = a[j + 1];
				a[j + 1] = a[i];
				a[i] = temp;
			}
		}
	}
}

void present(int a[], int n) {
	printf("\n");
	for (int i = 0;i <= n - 1;i++) {
		printf(" %d", a[i]);
	}
}

当然这并不是标准的选择排序，而是我自创的交换排序

哈基米说：

真正的选择排序： 在每一轮循环中，只记录最小值的下标（index），循环结束后只交换一次。

你的写法： 在每一轮循环中，只要发现比 a[i] 小的数，立刻交换。

这种写法的缺点：

  • 交换次数过多： 交换（读写内存）通常比比较（读取内存）更消耗性能。如果数列很乱，你的写法在每一轮里可能会发生多次交换。而标准选择排序每一轮只需交换 0 次或 1 次。

以及一个小不足：

循环写法： i <= n - 2 这种写法数学上是对的，但程序员通常习惯写 i < n - 1。两者等价，但后者可读性更强。

看看哈基米写的标准选择排序算法：

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h>

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

int main() {
    int a[7] = { 13, 38, 65, 97, 76, 49, 27 };
    
    printf("排序前:");
    present(a, 7);

    standard_selection_sort(a, 7);
    
    printf("排序后:");
    present(a, 7);
    return 0;
}

void standard_selection_sort(int a[], int n) {
    int i, j, minIndex, temp;

    // 外层循环：i 代表当前要确定的位置
    for (i = 0; i < n - 1; i++) {
        
        // 1. 假设当前位置 i 就是最小值
        minIndex = i;

        // 2. 内层循环：在剩下的元素中寻找真正的最小值
        for (j = i + 1; j < n; j++) {
            if (a[j] < a[minIndex]) {
                // 只记录下标，不进行交换！
                minIndex = j; 
            }
        }

        // 3. 只有当找到的最小值不是原来的 a[i] 时，才交换一次
        if (minIndex != i) {
            temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;
        }
    }
}

void present(int a[], int n) {
    for (int i = 0; i < n; i++) {
        printf(" %d", a[i]);
    }
    printf("\n");
}

我草啊啊啊啊，呃呃呃~~，哦哦哦！！！🥵🥵🥵

也是直接高潮了好吧，这个代码的思路太好了！

选择用minIndex储存下标值，最后检查下标值是否改变，就是检查后面的元素中有没有出现更小的值，再决定是否交换

反观我的代码，只要有更小的值就交换一次，如果多次检测到最小值的情况，就会交换多次，是一种效率上的浪费

我看了这个代码后重新写了一遍：

我认真写的代码：

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 selection_sort(int*, int);
void present(int*, int);

int main() {
	int a[7] = { 13,38,65,97,76,49,27 };
	selection_sort(a, 7);
	present(a, 7);
}

void selection_sort(int a[], int n) {
	for (int i = 0;i < n;i++) {
		int min_subscript = i,temp;
		for (int k = i + 1;k < n;k++) {
			if (a[k] < a[min_subscript]) {
				min_subscript = k;
			}
			if (min_subscript != i) {
				temp = a[min_subscript];
				a[min_subscript] = a[i];
				a[i] = temp;
			}
		}
	}
}

void present(int a[],int n) {
	for (int i = 0;i < n;i++) {
		printf(" %d", a[i]);
	}
}

能得出正确的排序，但我还是喂给了AI

看来我并没有那么聪明！🤣

哈基米思考了一会：

目前的写法虽然结果正确，但它仍然犯了和上一次类似的逻辑问题，导致它失去了选择排序最大的优势（最少的交换次数）。

这里有两个具体的建议和修改意见：

1. 致命问题：交换代码的位置不对

在“真正的选择排序”中，我们必须遍历完剩下的所有数字，找到那个唯一的最小值下标后，再进行交换。

你的代码问题： 你把交换的代码块 if (min_subscript != i) { ... } 放到了内层循环 for (int k ...) 的里面。

后果： 这意味着，在寻找最小值的过程中，只要你发现一个新的 min_subscript（或者甚至没发现），你都在尝试交换。这会导致每一轮外层循环中发生多次交换，效率变低。

修改方法： 只需移动一个花括号 } 的位置。把交换逻辑移到内层循环的外面。

2. 小建议：外层循环的边界

虽然写 i < n 没错，但对于选择排序，当循环到倒数第二个元素排好序时，最后一个元素自动就是最大的了。 所以标准写法通常是 i < n - 1。这能少跑一轮空循环（虽然对性能影响微乎其微，但显得更专业）。

修改后：

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
37
38
39
40
#include <stdio.h>

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

int main() {
    int a[7] = { 13,38,65,97,76,49,27 };
    selection_sort(a, 7);
    present(a, 7);
    return 0; // 养成好习惯，main函数最后加 return 0
}

void selection_sort(int a[], int n) {
    // 只需要处理到 n-1，最后一个数自动归位
    for (int i = 0; i < n - 1; i++) {
        int min_subscript = i;
        int temp;
        
        // 这一步只找最小值在哪里，绝对不碰数组里的值
        for (int k = i + 1; k < n; k++) {
            if (a[k] < a[min_subscript]) {
                min_subscript = k;
            }
        }

        // 找完之后，如果发现最小值不在开头，才进行唯一的交换
        if (min_subscript != i) {
            temp = a[min_subscript];
            a[min_subscript] = a[i];
            a[i] = temp;
        }
    }
}

void present(int a[], int n) {
    for (int i = 0; i < n; i++) {
        printf(" %d", a[i]);
    }
    printf("\n"); // 加上换行符，输出更美观
}

我也是牛逼哈，不断地犯错，甚至主函数的return 0;都忘记写了。

在哈基米的帮助下，我总算写对了。

哈基米有一句话让我受益匪浅：

总结： 你的逻辑核心（找最小值）是对的，只是动手的时机（交换）太早了。选择排序的精髓就是：多看（比较），少动（交换）。

排序和冒泡的优劣

研究这两个算法花了我不少时间，我于是向哈基米问了一下这两个算法的区别：

这两个排序算法（选择排序 vs 冒泡排序）其实是一对“难兄难弟”。

它们的时间复杂度在最坏和平均情况下都是 $O(n^2)$，也就是说，当数据量变大时，它们都会变得很慢。在实际的大型软件开发中（处理成千上万的数据），通常都不会用这两个，而是用更快的“快速排序”或“归并排序”。

不过，作为编程入门，它们非常重要。如果非要让它们两个PK一下，互有优劣，具体取决于你的使用场景：

1. 谁写内存（交换）更少？ —— 选择排序胜 🏆

这是选择排序最大的优势。

  • 选择排序： 无论数据多乱，它每一轮最多只交换 1 次。如果有 $n$ 个数，最多交换 $n-1$ 次。
  • 冒泡排序： 如果数据很乱（比如是倒序的），它每次比较都要交换。如果有 $n$ 个数，最坏情况下要交换 $n*(n-1)/2$ 次。

应用场景：

假设你在给老旧的单片机编程，或者在这个硬件上“写操作”非常消耗资源/寿命（比如早期的 Flash 存储器，写多了会坏），那么选择排序是更好的选择，因为它极大地减少了写入（交换）的次数。

2. 谁能利用“已经排好序”的部分？ —— 冒泡排序胜 🏆

  • 选择排序： 它是“死脑筋”。给它一个已经排好序的数列 {1, 2, 3, 4, 5}，它依然会傻傻地两层循环走完，去确认谁是最小值。
  • 冒泡排序（优化版）： 它是“机灵鬼”。如果在某一轮扫描中，发现一次交换都没有发生，它就知道“哦，数列已经排好了”，然后直接结束程序。

应用场景：

如果你知道你的数据大部分已经是排好序的，只有少数几个数乱了，用冒泡排序会快得飞起（接近 $O(n)$）。

3. 稳定性（Stability） —— 冒泡排序胜 🏆

这是一个进阶概念。假设你有两个 38，我们叫它们 38(A) 和 38(B)，且原本 38(A) 在 38(B) 前面。

  • 冒泡排序： 是稳定的。因为它是相邻比较，遇到相等的数不会交换。排完序后，38(A) 依然在 38(B) 前面。
  • 选择排序： 是不稳定的。因为它可能会把前面的 38(A) 交换到很后面的位置，破坏原有的相对顺序。

应用场景：

如果你在排“学生成绩单”，先按“学号”排了一次，现在要按“分数”再排一次。如果用不稳定的选择排序，分数相同的学生，学号顺序可能会被打乱。用冒泡排序则能保留学号的顺序。

总结对比表

特性 选择排序 (Selection Sort) 冒泡排序 (Bubble Sort)
交换次数 少 (固定 $O(n)$) 多 (取决于数据乱度)
比较次数 多 (固定 $O(n^2)$) 多 (通常 $O(n^2)$)
最佳情况速度 慢 (依然 $O(n^2)$) 快 (若已排序可达 $O(n)$)
稳定性 不稳定 稳定
逻辑复杂度 简单直观 简单直观

既然都学了，下一步做什么？

既然你已经掌握了这两种 $O(n^2)$ 的算法，而且代码写得越来越规范，我建议你挑战一个新的排序法，它也是 $O(n^2)$，但在小规模数据下，它通常比冒泡和选择都要快，而且更符合人类直觉。

它就是 **插入排序 (Insertion Sort)**。

原理就像打扑克牌： 摸一张牌，把它插到手里已经理好的牌中的正确位置。

想不想试试写一下插入排序？ (我可以给你提示，或者你自己先去查查原理)

详细探究一下排序法的不稳定性：

我看了AI给出的二者区别后，大受震撼，且对于排序法的不稳定性很好奇，于是我又问了问哈基米：

这个问题问得太好了！“稳定性”这个概念非常抽象，光看定义很难懂，但一旦画个图，你立刻就会明白。

所谓的 38(A) 和 38(B)，在计算机眼里数值都是 38。但为了区分它们，我们假设它们是两个不同的人：

  • 38(A)：是一个穿红衣服的人，排在前面。
  • 38(B)：是一个穿蓝衣服的人，排在后面。

我们希望：排完序后，红衣服依然在蓝衣服前面（这就叫稳定）。

如果排完序后，蓝衣服跑到红衣服前面去了（这就叫不稳定）。

1. 为什么选择排序是“不稳定”的？（案发现场）

选择排序的问题在于：它进行了一次“远距离暴力交换”。它为了把最小值拉到前面，不小心把本来坐在前面的 38(A) 扔到了后面去。

举个例子：

假设数列是：{ 38(A), 38(B), 10 }

目标： 从小到大排序。

第一轮循环 (i=0)：

  1. 我们要给第 0 个位置（现在坐着 38(A)）找一个最小值。
  2. 我们在后面找啊找，发现了 10 是最小的。
  3. 关键时刻来了！ 选择排序说：“我要把 10 放到第 0 个位置”。
  4. 于是，它把 10 和 38(A) 交换位置。

结果变成了：

{ 10, 38(B), 38(A) }

看！悲剧发生了：

本来 38(A) 在 38(B) 的前面。

但是因为 38(A) 运气不好，它占据了“坑位”，被用来交换那个最小的 10，结果被一脚踢到了数列的最后面。

现在的顺序变成了：蓝衣服(B) 在 红衣服(A) 的前面。

这就是不稳定。原有的顺序被打乱了。

2. 为什么冒泡排序是“稳定”的？（和谐社会）

冒泡排序是相邻两两比较。如果两个数一样大，它就不换。

还是那个例子：

数列：{ 38(A), 38(B), 10 }

第一轮冒泡：

  1. 比较 38(A) 和 38(B)。
    • 它俩一样大。冒泡排序的逻辑是 if (a[j] > a[j+1]) 才换。
    • 既然不大于（是等于），就不换。
    • 结果： 38(A) 依然稳稳地坐在 38(B) 前面。
  2. 接着比较 38(B) 和 10。
    • 38 比 10 大，交换！
    • 结果： { 38(A), 10, 38(B) }。

第二轮冒泡：

  1. 比较 38(A) 和 10。
    • 38 比 10 大，交换！
    • 结果： { 10, 38(A), 38(B) }。

最终结果：

{ 10, 38(A), 38(B) }

看到没？红衣服(A) 依然在 蓝衣服(B) 的前面。因为冒泡排序很温柔，不会跨越“人头”去扔东西，所以顺序保住了。

3. 这对“学生学号”有什么影响？

你可能会问：“这有啥用？反正都是38，谁在前谁在后不一样吗？”

对于简单的整数排序，确实没区别。但如果我们排的是复杂的对象（结构体），区别就大了。

场景模拟：

你在Excel里有一张成绩单，一开始是按学号排好序的：

学号 姓名 分数
001 张三 90
002 李四 90
003 王五 80

现在，老师要求：“按分数从低到高排序。”

如果是稳定的排序（如冒泡）：

排完分数后，分数相同的人，学号依然是有序的。

  1. 王五 (80分)
  2. 张三 (001号, 90分)
  3. 李四 (002号, 90分) -> 看着很舒服，同分的按学号排。

如果是不稳定的排序（如选择排序）：

排完分数后，可能会变成这样：

  1. 王五 (80分)
  2. 李四 (002号, 90分) -> 莫名其妙跑前面去了
  3. 张三 (001号, 90分)

这时候老师就会很困惑：“怎么李四排在张三前面？不是应该按学号顺延吗？”

总结：

  • 不稳定 = 容易“误伤友军”，为了换位置，把无辜的相同元素扔到了后面。
  • 稳定 = 讲究“先来后到”，原本谁在前面，排完序后（如果数值相等）它还在前面。

总结：

卧槽，要不是我多问一嘴，我还真不知道冒泡法和排序法有这么多不同，有这么多不同的运用场景

尤其是这个稳定性，看来我需要走的路还有很远！

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