选择排序（Selection Sort）

1. 选择排序原理

选择排序（Selection Sort）是一种简单直观的排序算法，基本原理如下：

寻找最小值：在未排序的部分中，找到最小的元素。
交换最小值与当前元素：将其与当前未排序部分的第一个元素交换。
重复步骤1-2，直到所有元素都排序完成。

2. 代码实现

#include <iostream>

using namespace std;

// **交换两个数**
void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

// **选择排序**
void selectionSort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        int minIndex = i;  // 记录最小值索引

        // **寻找当前未排序部分中的最小值**
        for (int j = i + 1; j < size; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // **交换最小值和当前未排序的起始位置**
        if (minIndex != i) {
            swap(arr[i], arr[minIndex]);
        }
    }
}

// **测试代码**
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "排序前：";
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    cout << endl;

    selectionSort(arr, size);  // 执行选择排序

    cout << "排序后：";
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    cout << endl;

    return 0;
}

3. 代码解析

外层循环 i：
- 逐步确定已排序部分，每次找到最小值并放置到 i 位置。
内层循环 j：
- 遍历未排序部分，找到最小值的索引 minIndex。
交换元素：
- 将 minIndex 位置的最小值与 i 位置的元素交换，确保 i 之前的元素有序。

4. 时间复杂度分析

最优、最差、平均时间复杂度

无论数据是否有序，选择排序的比较次数都固定为 O(n²)：
- 外层循环执行 n-1 次
- 内层循环最多 n-1、n-2……1 次
- 总比较次数：O(n²)
交换次数（比冒泡排序少）
- 每轮最多1次交换，最多 n-1 次，最少 0 次。
- 最坏情况：O(n) 次交换。