选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

算法思路

1. 使用线性查找当前待排序数据，找到最小值
2. 把最小值移动到数组最左边
3. 重复1、2步，直到数组全部完成排序

代码实现

方式一：

使用递归实现，一次循环比较好读，容易理解，但效率较循环低一些

const unsort = [6, 1, 7, 8, 9, 3, 5, 4, 2]

const selectedSort = (arr, index = 0) => {  
    let min = arr[index]

    const len = arr.length

    for (let i = index; i < len; i++) {
        const temp = arr[i]
        if (temp < min) {
            arr[index] = temp
            arr[i] = min
            min = temp
        }
    }

    if (index === len - 1) {
        return arr
    }
    return selectedSort(arr, index + 1)
}

const sorted = selectedSort(unsort)

console.log(sorted)

// console: [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

方式二：

使用循环实现，两次循环，比较不好读，逻辑容易出现纰漏，效率比递归要高

const unsort = [6, 1, 7, 8, 9, 3, 5, 4, 2]

const selectedSort = (arr) => {
    const len = arr.length
    let min
    let temp
    for (let i = 0; i < len; i++) {
        min = arr[i]
        temp
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < min) {
                temp = min
                min = arr[j]
                arr[j] = temp
                arr[i] = min
            }
        }
    }
    return arr
}

const sorted = selectedSort(unsort)

console.log(sorted)

// console: [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

理解

选择排序使用线性方式来查找最小值，所以每次循环都会比较n-m(m为循环次数)个数，直到最后一轮只比较一个数字，因此复杂度是（n - 1）+ (n - 2) + (n - 3) ... + 1 ≈ n² / 2, 忽略非重要项后为O(n²)