🎯 选择排序 (Selection Sort)

归档: #Algorithm #Sorting #Elementary

核心心法: "狙击手" —— 瞄准乱堆里最小的那个，一枪带走。

🧠 核心思想

它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置。

• 每一轮只做一次交换（或者不交换）。
• 无论数组多乱或多有序，它都要老老实实扫描一遍。

🎨 图解演示

点击“开始排序”体验狙击过程

29

0

10

1

14

2

37

3

14

4

25

5

8

6

32

7

17

8

5

9

💻 代码实现 (C++)

void selectionSort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i; // 假设当前位置 i 就是最小的
        
        // 🔭 在后面剩下的堆里找个更小的
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[minIndex]) {
                minIndex = j; // 更新最小值的下标
            }
        }
        
        // 找到了真正的最小(minIndex)，把它换到前面(i)来
        swap(nums[i], nums[minIndex]);
    }
}

📊 复杂度分析

维度	数值	说明
时间 (平均)		即使数组有序，也要 次比较
时间 (最好)		没得商量，它是“最诚实”的算法
空间		原地交换
稳定性	❌ 不稳定	跨距离交换可能破坏相对顺序 (如 5, 8, 5, 2 交换第一个5和2)

💡 适用场景

• 写操作非常昂贵时：如果你交换数据的成本很高（写磁盘），选择排序是很好的选择，因为它最多只交换 次（冒泡和插入可能交换 次）。