选择排序

每次从未排序部分选择最小值，放到已排序部分的末尾。

思路

• 外层循环控制已排序部分的边界
• 内层循环在未排序部分找到最小值的索引
• 将最小值与已排序部分末尾的下一个位置交换
• 重复直到所有元素排序完成

代码

// 选择排序
// 每次找到未排序部分的最小值，然后放到已排序部分的末尾

function selectionSort(arr) {
    for(let i = 0; i < arr.length - 1; i++) {
        // 最后一个元素不用管
        let min = i;
        for(let j = i + 1; j < arr.length; j++) {
            if(arr[j] < arr[min]){
                min = j;
            }
        }
        if(min !== i){
            [arr[i], arr[min]] = [arr[min], arr[i]];
        }
    }
}

复杂度

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$
• 稳定性：不稳定