从头实现选择排序

思路：不是见到更小的元素时就交换位置，而是在找到最小的元素时才交换位置。遍历数组的前 n - 1 个元素，从它们及之后的元素中找到最小的元素，与它们交换位置。

数组有 n 个元素，在从第 1 个元素开始的所有 n 个元素中找到最小元素，与第 1 个元素交换位置；在从第 2 个元素开始的所有 n - 1 个元素中找到最小元素，与第 2 个元素交换位置；……；在从第 n - 1 个元素开始的所有 2 个（n - i + 1）元素中找到最小元素，与第 n - 1 个元素交换位置。

框架：

#include <algorithm>
#include <iostream>
#include <vector>

void SelectionSort(std::vector<int> &A) {

}

int main() {
    std::vector<int> A{9, 1, 5, 8, 3, 7, 4, 6, 2};
    SelectionSort(A);
    std::ranges::for_each(A, [](int value) { std::cout << value << ' '; });
    return 0;
}

遍历前 n - 1 个元素。

void SelectionSort(std::vector<int> &A) {
    for (int i = 0; i < A.size() - 1; ++i) {

    }
}

创建一个变量min，用于记录在本次遍历过程中遇到的当前最小元素的索引。用合适的值初始化它。

void SelectionSort(std::vector<int> &A) {
    for (int i = 0; i < A.size() - 1; ++i) {
        int min = i;

    }
}

创建一个内层循环，目的是从当前元素及之后的元素中，找到最小元素的索引。

void SelectionSort(std::vector<int> &A) {
    for (int i = 0; i < A.size() - 1; ++i) {
        int min = i;
        for (int j = i; j < A.size(); ++j) {

        }

    }
}

如果内层循环当前遍历到的元素比min中索引处的元素小，更新min中的记录。

void SelectionSort(std::vector<int> &A) {
    for (int i = 0; i < A.size() - 1; ++i) {
        int min = i;
        for (int j = i; j < A.size(); ++j) {
            if (A[j] < A[min]) {
                min = j;
            }
        }

    }
}

在内层循环遍历完毕后，min中的索引就是从外层循环当前元素开始及之后的所有元素中的最小元素的索引，交换最小元素与当前元素的位置。
(使用已定义函数void Swap(int&, int&);)

void SelectionSort(std::vector<int> &A) {
    for (int i = 0; i < A.size() - 1; ++i) {
        int min = i;
        for (int j = i; j < A.size(); ++j) {
            if (A[j] < A[min]) {
                min = j;
            }
        }

        Swap(A[i], A[min]);
    }
}

完整代码：

#include <algorithm>
#include <iostream>
#include <vector>

void Swap(int &i, int &j) {
    int temp = i;
    i = j;
    j = temp;
}

void SelectionSort(std::vector<int> &A) {
    for (int i = 0; i < A.size() - 1; ++i) {
        int min = i;
        for (int j = i; j < A.size(); ++j) {
            if (A[j] < A[min]) {
                min = j;
            }
        }

        Swap(A[i], A[min]);
    }
}

int main() {
    std::vector<int> A{9, 1, 5, 8, 3, 7, 4, 6, 2};
    SelectionSort(A);
    std::ranges::for_each(A, [](int value) { std::cout << value << ' '; });
    return 0;
}