选择排序——像整理试卷一样，每次挑出最小的

什么是选择排序？

选择排序是一种简单直观的排序算法。它的核心思想就像你整理一堆散乱的试卷：先找出分数最低的那张，放到第一张的位置；然后在剩下的试卷中再找最低的，放到第二张……一直这样重复，直到所有试卷按分数从小到大排好。每轮都从未排序的部分中挑出最小的元素，放到已排序部分的末尾。

相比冒泡排序（每次交换相邻元素），选择排序的交换次数更少——每轮最多交换一次。如果你要排序的数据量不大（比如几十个数字），用选择排序既容易理解，又方便实现。

思路与生活比喻

想象你在课桌上有一堆杂乱的卡牌（数字），你想把它们从小到大排好：

第一轮：从头到尾看一遍所有牌，找出最小的一张（假设是10），把它放到最左边第一个位置（原来那张29被换到10的位置）。
第二轮：忽略已经排好的第一张10，从第二张开始往后看，找到剩余牌中的最小（13），把它放到第二个位置（与29交换）。
第三轮：忽略前两张，从第三张开始看……就是这样，每轮“选择”出当前最小的数字，放到它应该在的位置。

你可以想象自己是在玩扑克牌整理，或者体育老师让同学们按身高从小到大排队。老师每次从队伍中找出最矮的同学，让他站到第一个；然后再从剩下的人中找出最矮的，站到第二个……直到所有人站好。

图解过程：用例子一步步看

假设我们要排序的数组是 [29, 10, 14, 37, 13]（5个数字）。

初始状态

索引: 0   1   2   3   4
数值: 29  10  14  37  13
已排序部分：[]（空）
未排序部分：[29,10,14,37,13]

第一轮（i=0）

假设最小值索引 minIndex = 0（值为29）
从索引1开始扫描：10 < 29 → minIndex=1；14>10不变；37>10不变；13>10不变
找到最小值10在索引1，与当前索引0交换 → 数组变为 [10, 29, 14, 37, 13]
已排序部分：[10]；未排序部分：[29,14,37,13]

第二轮（i=1）

假设最小值索引 minIndex = 1（值为29）
从索引2扫描：14 < 29 → minIndex=2；37>14不变；13<14 → minIndex=4
找到最小值13在索引4，与当前索引1交换 → 数组变为 [10, 13, 14, 37, 29]
已排序部分：[10,13]；未排序部分：[14,37,29]

第三轮（i=2）

假设最小值索引 minIndex = 2（值为14）
从索引3扫描：37>14不变；29>14不变
最小值14已经在正确位置，不需要交换 → 数组不变 [10, 13, 14, 37, 29]
已排序部分：[10,13,14]；未排序部分：[37,29]

第四轮（i=3）

假设最小值索引 minIndex = 3（值为37）
从索引4扫描：29 < 37 → minIndex=4
找到最小值29在索引4，与当前索引3交换 → 数组变为 [10, 13, 14, 29, 37]
已排序部分：[10,13,14,29]；未排序部分：[37]

第五轮？不需要

当只剩下一个元素（最后一个37）时，它已经是最大的了，自动排好。所以循环只需要执行 n-1 轮（这里 n=5，执行4轮）。

最终结果：[10, 13, 14, 29, 37] ✅

代码实现（带详细注释）

下面的C++代码演示了选择排序的实现。每一行变量定义都加上了中文注释，方便你理解。

#include <iostream>
using namespace std;

// 选择排序函数
void selectionSort(int arr[], int n) {            // arr:待排序数组, n:元素个数
    for (int i = 0; i < n - 1; i++) {            // 外层循环：i表示当前要放最小值的位置
        int minIndex = i;                        // minIndex:记录当前轮最小值的下标，先假设是i
        for (int j = i + 1; j < n; j++) {        // 内层循环：从i的下一个位置开始扫描
            if (arr[j] < arr[minIndex]) {        // 如果发现更小的数
                minIndex = j;                    // 更新最小值的下标
            }
        }
        // 如果最小值不在当前位置，才需要交换
        if (minIndex != i) {
            int temp = arr[i];                   // temp:临时保存当前位置的值
            arr[i] = arr[minIndex];              // 把最小值放到当前位置
            arr[minIndex] = temp;                // 把原来的值换到最小值原来的位置
        }
    }
}

int main() {
    int arr[] = {29, 10, 14, 37, 13};           // arr:待排序的数组
    int n = 5;                                    // n:数组长度
    selectionSort(arr, n);                        // 调用排序函数
    for (int i = 0; i < n; i++) {                // 输出排序后的结果
        cout << arr[i] << " ";
    }
    return 0;
}

代码要点解释

外层循环 for (int i = 0; i < n-1; i++)：循环 n-1 次，因为最后一个元素不需要再处理。
minIndex = i：每轮开始时假设当前位置就是最小值的位置。
内层循环 for (int j = i+1; j < n; j++)：扫描未排序部分（从 i+1 到末尾），找出真正的最小值下标。
交换：如果 minIndex != i，说明最小值不在当前位置，交换两个位置的元素。如果已经在正确位置，就不需要交换（减少不必要的操作）。
变量注释：每个变量定义时都用“变量名:中文含义”的格式注释，例如 int temp = arr[i]; // temp:临时保存当前位置的值。

时间复杂度和特点

时间复杂度：无论数组最初有序还是无序，都需要两层循环：外层循环 n-1 次，内层循环次数逐渐减少（n-1, n-2, ..., 1）。总的比较次数为 (n-1)+(n-2)+...+1 = n(n-1)/2，所以时间复杂度为 O(n²)。
空间复杂度：只用了几个额外的变量（i, j, minIndex, temp），所以是 O(1)，属于原地排序。
稳定性：选择排序是不稳定的。例如数组 [5, 5, 3]，第一轮找到最小3，与第一个5交换，两个5的相对顺序就变了。如果你需要稳定排序（相等元素保持原顺序），应该选择插入排序或归并排序。
比较次数多，交换次数少：比冒泡排序的交换次数少很多（冒泡排序最坏情况下每轮可能交换多次）。适合数据量不大（比如 n<1000）且交换操作比较耗时的场景。

新手容易犯的错误

忘记更新 minIndex
错误写法：只判断 arr[j] < arr[i]，然后直接交换。这样每次只和当前位置比较，而没有记录真正的最小值下标。正确做法是用 minIndex 记录最小值的下标，一轮结束后才交换。
内层循环边界写错
错误：for (int j = i; j < n; j++) 这样会把当前位置自己和自己比较，不影响结果但多了一次无用比较。更规范的是从 i+1 开始。
交换条件判断错误
如果不加 if (minIndex != i)，即使最小值已在正确位置，也会自己和自己交换（不影响正确性，但多了一次赋值操作）。加判断可以稍微提高效率。
外层循环多执行一轮
错误：for (int i = 0; i < n; i++) 会执行 n 轮。当只剩下最后一个元素时，不需要再比较，所以应该是 i < n-1。
忘记包含头文件
使用 cout 需要 #include <iostream>，否则编译会报错。

完整可运行的示例（包含输入和输出）

下面是一个完整的程序，你可以直接复制到你的编译器运行。它从控制台读取5个数字，然后排序并输出。

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {            // arr:待排序数组, n:元素个数
    for (int i = 0; i < n - 1; i++) {            // i:当前要放置最小值的位置
        int minIndex = i;                        // minIndex:当前轮最小值下标
        for (int j = i + 1; j < n; j++) {        // j:扫描指针
            if (arr[j] < arr[minIndex]) {        // 找到更小的数
                minIndex = j;                    // 更新最小值下标
            }
        }
        if (minIndex != i) {                     // 如果最小值不在当前位置
            int temp = arr[i];                   // temp:临时变量
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

int main() {
    int n = 5;                                    // n:数组长度
    int arr[5];                                   // arr:存储输入的5个数字
    cout << "请输入5个整数，用空格隔开：";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];                            // 读取用户输入
    }

    selectionSort(arr, n);                        // 排序

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

    return 0;
}

运行示例：

请输入5个整数，用空格隔开：29 10 14 37 13
排序后的结果：10 13 14 29 37

选择排序——每次挑出最小的