C语言排序——选择排序

原理

开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。

设数组的长度为 𝑛 :

初始状态下，所有元素未排序，即未排序（索引）区间为 [0, 𝑛 − 1] 。
选取区间 [0, 𝑛 − 1] 中的最小元素，将其与索引 0 处元素交换。完成后，数组前 1 个元素已排序。
选取区间 [1, 𝑛 − 1] 中的最小元素，将其与索引 1 处元素交换。完成后，数组前 2 个元素已排序。
以此类推。经过 𝑛 − 1 轮选择与交换后，数组前 𝑛 − 1 个元素已排序。
仅剩的一个元素必定是最大元素，无须排序，因此数组排序完成。

示例

“4 1 3 1 5 2”

第一轮：

初始未排序区间为“4 1 3 1 5 2”，在这个区间中找到最小的元素是 1（第一个位置的 1）。
将这个最小的元素 1 与未排序区间的第一个元素 4 交换位置，此时序列变为“1 4 3 1 5 2”。已排序区间为“1”，未排序区间为“4 3 1 5 2”。

第二轮：

未排序区间为“4 3 1 5 2”，找到其中最小的元素是 1（第三个位置的 1）。
将这个最小的元素 1 与未排序区间的第一个元素 4 交换位置，此时序列变为“1 1 3 4 5 2”。已排序区间为“1 1”，未排序区间为“3 4 5 2”。

第三轮：

未排序区间为“3 4 5 2”，找到其中最小的元素是 2。
将最小元素 2 与未排序区间的第一个元素 3 交换位置，此时序列变为“1 1 2 4 5 3”。已排序区间为“1 1 2”，未排序区间为“4 5 3”。

第四轮：

未排序区间为“4 5 3”，找到其中最小的元素是 3。
将最小元素 3 与未排序区间的第一个元素 4 交换位置，此时序列变为“1 1 2 3 5 4”。已排序区间为“1 1 2 3”，未排序区间为“5 4”。

第五轮：

未排序区间为“5 4”，找到其中最小的元素是 4。
将最小元素 4 与未排序区间的第一个元素 5 交换位置，此时序列变为“1 1 2 3 4 5”。已排序区间为“1 1 2 3 4 5”，未排序区间为空，排序完成。

代码（C）

void selectionSort(int nums[], int n) {
    // 外循环：未排序区间为 [i, n - 1]
    for (int i = 0; i < n - 1; i++) {
        // 这里的 i 表示当前已排序区间的末尾位置，每一轮循环会将未排序区间中的最小元素放到这个位置
        // 初始时，已排序区间为空，随着循环进行，已排序区间逐渐扩大

        // 内循环：找到未排序区间内的最小元素
        int k = i; // k 用于记录当前未排序区间中最小元素的索引，初始值设为 i，表示假设当前位置的元素是最小的

        for (int j = i + 1; j < n; j++) {
            // 遍历未排序区间 [i + 1, n - 1]，寻找最小元素
            if (nums[j] < nums[k]) {
                k = j;// 如果找到比当前最小元素更小的元素，更新 k 为该元素的索引
            }
        }
        // 将该最小元素与未排序区间的首个元素交换
        int temp = nums[i];
        nums[i] = nums[k];
        nums[k] = temp;// 交换操作确保未排序区间的最小元素被放到已排序区间的末尾位置
    }
}