# 选择排序（稳定）

时间复杂度：O(n²)

# 思想

经过 第 i 次 后，能将新数组 下标为 i 的元素 选择出来。（0 < i < len - 1）

const selectSort = arr => {
    let len = arr.length;

    for (let i = 0; i < len - 1; i++) { // 注意此处为 i < len - 1
        let min = arr[i];

        for (let j = i + 1; j < len; j++) {
            if (arr[j] < min) {
                [min, arr[j]] = [arr[j], min]
            }
        }

        arr[i] = min;
    }
    return arr;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 大致步骤

在待排序列中找到最小元素，存放到已排序序列的起始位置；然后再从剩余未排序元素中，继续寻找最小元素，放到已排序列的末尾。

# 具体步骤

一共比较length - 1轮，当前第i轮（i代表的是第i个位置应该放什么数）
每轮会把第i个位置的数拷贝到min
将第i个位置后面的每个数都和这个min比较
如果比较后符合条件，交换位置（即把更小的数放到min，把min里的数放到这个数的位置）
该轮结束后，把min里的数赋值到第i个位置上

例子：[1, 9, 7, 6]

一共进行3轮，当前第1轮
把第一个位置的数（1）拷贝到min
将9和1比较，不换
将7和1比较，不换
将6和1比较，不换，本轮结束，将min赋值到第一个位置上，数组为[1, 9, 7, 6]
把第二个位置的数（9）拷贝到min
将7和9比较，换。此时min=7，数组为[1, 9, 9, 6]
将6和7比较，换。此时min=6，数组为[1, 9, 9, 7]，本轮结束，将min赋值到第二个位置上，数组为[1, 6, 9, 7]
把第三个位置的数（9）拷贝到min
将7和9比较，换。此时min=7，数组为[1, 6, 9, 9]，本轮结束，将min赋值到第三个位置上，数组为[1, 6, 7, 9]
最终数组[1, 6, 7, 9]