选择排序：像挑选苹果一样把最小的挑出来

选择排序——像挑苹果一样，把最小的逐个挑出来

你一定有过这样的经历：面前有一筐大小不一的苹果，你想把它们从小到大排整齐。最简单的方法就是——先找出最小的那个，放在第一个位置；然后从剩下的苹果里再找出最小的，放在第二个位置……如此反复，直到所有苹果都排好。选择排序（Selection Sort）就是这样一种朴素而直观的排序方法。它适合用来对少量数据排序，比如班级里几个同学的身高、考试分数，或者你口袋里的零花钱数目。

算法思想：每轮“选秀”，挑出最小的

选择排序的核心思路可以概括为三步：

从未排序部分中找到最小的元素（就像从一堆同学里选出个子最矮的）。
把这个最小元素与未排序部分的第一个元素交换（让最矮的同学站到队伍最前面）。
已排序部分增加一个，未排序部分减少一个，重复上述过程，直到全部排好。

如果我们把数据看作一个数组，那么“已排序部分”在数组的最左边，“未排序部分”在右边。每一轮，我们都在未排序部分里“选择”最小的，把它放到已排序部分的末尾（即未排序部分的第一个位置）。

详细举例：用数组 `[4, 2, 8, 1]` 走一遍

初始数组（下标从0开始）：

下标	0	1	2	3
值	4	2	8	1

第一轮（i = 0）：找出整个数组中最小的数

从下标0到3依次看：4, 2, 8, 1 → 最小的是1（下标3）。
把1和第一个数4交换 → [1, 2, 8, 4]
此时下标0已经排好（就是最小的1）。

第二轮（i = 1）：从下标1开始找最小的数

看下标1到3：2, 8, 4 → 最小的是2（下标1）。它已经在正确位置，不需要交换 → [1, 2, 8, 4]。

第三轮（i = 2）：从下标2开始找最小的数

看下标2到3：8, 4 → 最小的是4（下标3）。
交换8和4 → [1, 2, 4, 8]

排序完成！每一轮我们确实是从剩下的数字中“选择”最小的放到前面。

如果你手里有5个苹果，大小分别是 [7, 3, 9, 2, 6]，用同样的方法也能轻松排好：

第一轮找全局最小2，与7交换 → [2, 3, 9, 7, 6]
第二轮从下标1开始，最小是3（已在原位）→ 不变
第三轮从下标2开始，最小是6（下标4），与9交换 → [2, 3, 6, 7, 9]
第四轮从下标3开始，最小是7（已在原位）→ 不变
结束。

可见选择排序的执行步骤非常固定，无论数组是否已经有序，它都会老老实实地走完所有轮次。

C++ 代码实现（保留原始代码并补充中文注释）

下面是完整的代码，每一行变量定义都写了中文注释，方便理解：

#include <iostream>
using namespace std;

int main() {
    int arr[] = {4, 2, 8, 1};   // 待排序的数组
    int n = 4;                  // 数组长度

    // 外层循环：处理 n-1 轮（最后只剩一个元素时不用再选）
    for (int i = 0; i < n - 1; i++) {
        // 假设当前 i 位置就是未排序部分中最小的
        int minIndex = i;

        // 内层循环：在 i 后面的数字中找真正最小的
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;  // 发现更小的，更新最小数下标
            }
        }

        // 如果最小的不在 i 位置，就交换
        if (minIndex != i) {
            int temp = arr[i];          // 临时保存 arr[i]
            arr[i] = arr[minIndex];     // 把最小的放到前面
            arr[minIndex] = temp;       // 把原来的数放到后面
        }
    }

    // 输出排序后的数组
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

运行结果：

1 2 4 8

如果想处理用户输入的数组，可以这样改写（仅作补充，不影响原有核心代码）：

#include <iostream>
using namespace std;

int main() {
    int arr[100];               // 假设最多100个数
    int n;                      // 实际个数

    cout << "请输入数字个数：";
    cin >> n;

    cout << "请输入 " << n << " 个整数（空格隔开）：";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];          // 逐个读取
    }

    // 选择排序核心代码（与上面相同）
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;       // 假设当前下标 i 是最小值位置
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;   // 更新最小值下标
            }
        }
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    cout << "排序结果：";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

新手容易犯的错误

内层循环的起始值写错
有的人会把 j = i + 1 写成 j = 0 或 j = i。如果写成 j = 0，每轮都会从开头找最小值，导致已经排好的部分被再次选中甚至交换，打乱顺序；如果写成 j = i，则 arr[i] 会和自己比较一次，虽然不会出错但浪费一次比较。
忘记 minIndex 的初始化
有的同学会忘记在每轮开始时把 minIndex 设为 i，结果用了上一轮的旧值，就会把最小位置的初始值搞错。
交换条件写反或不加判断
正确的做法是：只有当 minIndex != i 时才交换。如果无条件交换（minIndex 等于 i 时也交换），虽然结果可能一样（和自己交换没意义），但多了一次无用的赋值。另外，如果把 if (arr[j] < arr[minIndex]) 写反成大于号，就会变成从大到小排序。
数组越界
内层循环 j < n，如果写成 j <= n，当 j == n 时数组访问越界，程序可能崩溃。

选择排序的特点

交换次数少：最多进行 n-1 次交换（每轮最多一次），而冒泡排序最坏情况下需要交换 n*(n-1)/2 次。因此选择排序在数据交换成本高（比如交换两个结构体变量）时比冒泡排序有优势。
比较次数固定：无论数据是否有序，选择排序都要比较 n*(n-1)/2 次，即时间复杂度总是 O(n²)。所以它比插入排序（最好情况下 O(n)）要慢一些。
不稳定：选择排序可能会改变相同数值元素的相对顺序。例如数组 [5a, 5b, 3]（用 a、b 区分两个相同的 5），第一轮找到最小 3，与 5a 交换后变成 [3, 5b, 5a]，原来在后面的 5b 跑到了 5a 前面，所以不稳定。如果排序对象是整数，不稳定可能无所谓；但如果排序对象是带有其他信息的结构体（比如按分数排序学生，相同分数希望保持原来顺序），就需要考虑稳定性。

与冒泡排序、插入排序的对比

排序方法	交换次数（最好/最坏）	比较次数	稳定性	适用场景
冒泡排序	0 / O(n²)	O(n²)	稳定	基本有序时效果好（可优化）
选择排序	0 / O(n)	O(n²)	不稳定	数据量小且交换成本高时
插入排序	0 / O(n²)	O(n²)	稳定	基本有序效果最好

选择排序比冒泡排序“聪明”的地方在于：它每轮只做一次交换，而不是像冒泡那样相邻比较后频频交换。但它的比较次数和冒泡一样多，所以整体速度仍然较慢。对于几百个数字以内的排序，选择排序的直观性使它成为初学者的好伙伴。