一、选择排序核心概念

选择排序（Selection Sort）是一种简单直观的排序算法，核心思想： 把数组分为「已排序区间」和「未排序区间」，每次从「未排序区间」中找到最小（或最大）的元素，放到「已排序区间」的末尾，重复这个过程直到整个数组有序。

可以类比生活中的场景：整理一堆杂乱的书本，每次从剩下的书里挑出最薄的一本，放到已整理好的书堆最后，直到所有书都整理完。

二、选择排序工作原理（以升序排序为例）

假设待排序数组为 [5, 2, 9, 1, 5, 6]，下标从0开始（编程常用写法），排序过程分6步（数组长度为6）：

三、选择排序代码实现（C++版，带详细注释）

#include<iostream>
using namespace std;

// 选择排序函数：对数组arr进行升序排序，n为数组长度
void selectionSort(int arr[], int n) {
    // 外层循环：控制已排序区间的末尾（i是未排序区间的第一个元素下标）
    for (int i = 0; i < n - 1; i++) {
        // 1. 初始化最小值下标为未排序区间的第一个元素
        int minIndex = i;
        
        // 2. 内层循环：遍历未排序区间，找到最小值的下标
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j; // 更新最小值下标
            }
        }
        
        // 3. 交换：把最小值放到未排序区间的第一个位置（已排序区间末尾）
        if (minIndex != i) { // 优化：如果最小值就是当前元素，无需交换
            swap(arr[i], arr[minIndex]);
        }
    }
}

int main() {
    // 测试用例
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度
    
    cout << "排序前数组：";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    
    // 调用选择排序函数
    selectionSort(arr, n);
    
    cout << "排序后数组：";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    
    return 0;
}

代码关键解释：

1. 外层循环 i：i 表示「已排序区间」的末尾下标+1（即「未排序区间」的第一个下标），循环到 n-1 即可（最后一个元素无需处理）；
2. 内层循环 j：从 i+1 开始遍历未排序区间，找到最小值的下标 minIndex；
3. 交换操作：用 swap 函数交换 arr[i] 和 arr[minIndex]，把最小值放到已排序区间末尾；
4. 优化点：判断 minIndex != i，避免自身交换（不影响结果，但能减少无意义操作）。

输出结果：

排序前数组：5 2 9 1 5 6 
排序后数组：1 2 5 5 6 9 

四、选择排序的特性分析

1. 时间复杂度

• 最好情况：O(n²)（即使数组已有序，仍需遍历找最小值）；
• 最坏情况：O(n²)；
• 平均情况：O(n²)。 → 适合小规模数据排序，大规模数据效率低。

2. 空间复杂度

O(1)：只用到临时变量，是原地排序算法（不需要额外开辟数组）。

3. 稳定性

选择排序是不稳定排序（稳定性：排序后相等元素的相对位置不变）。 举例：数组 [2, 3, 2, 1]，第一次找最小值1（下标3），交换下标0和3 → [1, 3, 2, 2]，原数组中第一个2（下标0）和第二个2（下标2）的相对位置被改变。

五、新手常见问题解答

1. 为什么外层循环到 n-1 而不是 n？ 当 i = n-1 时，未排序区间只剩最后一个元素，本身就是有序的，无需处理。

2. 如何改成降序排序？ 只需把内层循环的判断条件从 arr[j] < arr[minIndex] 改为 arr[j] > arr[maxIndex]（同时把 minIndex 改为 maxIndex）。

3. 和插入排序的区别？

   • 插入排序：边找位置边移动元素，每轮只移动比当前元素大的元素；
   • 选择排序：先找最小值，再一次性交换，每轮最多1次交换。

总结

1. 核心逻辑：选最小值（或最大值）→ 交换到已排序区间末尾，重复至有序；
2. 代码关键：外层循环定区间，内层循环找最值，最后交换元素；
3. 特性：简单易实现、原地排序，但时间复杂度高（O(n²)）、不稳定，适合小规模数据排序。

通过这个教程，你可以快速理解选择排序的原理和实现，建议自己动手修改代码（比如改成降序、测试不同数组），加深对算法的理解。