选择排序模板

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a[] = {5, 3, 8, 1, 2};
    int n = 5;

    // 选择排序
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[minIdx])
                minIdx = j;
        }
        if (minIdx != i) swap(a[i], a[minIdx]);
    }

    for (int x : a) cout << x << " ";  // 1 2 3 5 8
    cout << endl;

    return 0;
}

📖 要点说明

• 时间复杂度 O(n²)，空间 O(1)
• 每轮找最小值下标，找到后与当前位置交换
• 交换次数最少（每轮最多一次），但比较次数固定
• 不稳定排序：如 5a 5b 3，交换后 5a 和 5b 顺序变了

⚠️ 常见错误

• 找最小值时忘更新 minIdx
• 内层从 i+1 开始不是 i
• 不稳定排序可能导致相等元素顺序改变