选择排序

选择排序（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²)