排序算法(一)--选择排序

选择排序的思想：将数组的第一项，与后面的每一项做对比，找到最小的那一个，放到第一位，将剩余项所组成的数组的第一项与后面的每一项做对比，找到最小的项放到第一位，以此类推，时间复杂度为n²。

var selectSort = (arr) => {
    for (let i = 0; i < arr.length - 1;i++) {
        let minPos = i
        for (let j = i + 1; j < arr.length;j++) {
            minPos = arr[j] < arr[minPos] ? j : minPos
        }
        let temp = arr[i]
        arr[i] = arr[minPos]
        arr[minPos] = temp
    }
    return arr
}
selectSort([7,3,1,5,2,4,6,9,8])
// [1,2,3,4,5,6,7,8,9]

上面的方法是通过找最小值来实现的。那么，我们既然能找到最小值，同时，我们是不是也可以找到最大值呢？这样以来遍历就可以减少一半了，当然是可以的了，且看下面的代码。

var selectSort = (arr) => {
    let left = 0
    let right = arr.length - 1
    while(left < right) {
        let min = left
        let max = right
        for(let i = left;i <= right;i++) {
            min = arr[i] < arr[min] ? i : min
            max = arr[max] < arr[i] ? i : max
        }
        if (arr[min] < arr[left]) {
            let temp = arr[left]
            arr[left] = arr[min]
            arr[min] = temp
        }
        if (arr[max] > arr[right]) {
            let temp = arr[right]
            arr[right] = arr[max]
            arr[max] = temp
        }
        left++
        right--
    }
    return arr
}
selectSort([7,3,1,5,2,4,6,9,8])
// [1,2,3,4,5,6,7,8,9]

注意：选择排序的是一种不稳定的排序，如果出现俩个相邻的值相等，那么往往前一个值会跑到后一个值后面。