选择排序

选择排序是冒泡排序的升级版

基本原理

每次排序(互换位置)前，先从没排序的数列里面选出最小值，然后再把选中的最小值和目标值交换位置

比如，第一次排序，所有元素(n)都是未排序的，就在所有元素里选出最小值，然后将这个最小值和第一个位置互换，然后第二次在剩余的元素(n-1)里先选出最小值（也就是全部元素(n)的第二小值），然后把最小值和第而个值互换位置，…以此类推，知道找到第n-1个元素和n互换位置后，第n个位置不用比较了，因为他就是最大值。

复杂度

最好复杂度O(n²)

最差复杂度O(n²)

因为选择排序是每次先找出一个最值，然后再进行互换位置，虽然比较次数还是O(n²)，但是交换次数由O(n²)减到O(n)

稳定性

稳定算法，所有相同元素相对位置都不变

不稳定算法，只要有一个相同元素的相对位置变了，他就是不稳定的

举个应用的例子： ABCDE排队办事，然后每个人办事所用时长对应上面表里面的数字，也就是：A5,B8,C5,D2,E9；这时候为了减少办事整体时间，就优先从用时最短的开始办起，于是乎排个序；如果是稳定排序，则应该是：D2,A5,C5,B8,E9，合情合理、相安无事；如果是不稳定的，就如上面提到的选择排序，那排序结果就变成：D2,C5,A5,B8,E9，很显然排序之后本应该在A后面的C跑到前面去了，如果这是现实排队的话，说不定两人就排队的先来后到原则发生争执，开始真人PK了。

选择排序，如果当前元素(a)比一个对比的元素(b)小，而该对比的元素(b)又出现在一个和当前元素(a)相等的元素后面，那么交换后稳定性就被破坏了。

举个的例子：从小到大排列，[3(0),3(1),1(2)]，第一次，第一个3回合最后的2互换位置，则结果：[1(2),3(1),3(0)]，此时已经原序列的两个3顺序就被破坏了

然后第二次，下标为1的3和自己交换位置

最后第三次，下标为2的3和自己交换位置

最终原始的两个3的顺序变了（即现在两个相同的三下标值是1,0），即不稳定（如果是稳定的话，则结果应该是[1(2),3(0),3(1)]）

function selectionSort(arr) {
    for (var j = 0; j < arr.length; j++) {
        var min = j //记录最小值的下标
        for (var i = min + 1; i < arr.length; i++) {
            if (arr[min] > arr[i]) {
                min = i
            }
        }
        var temp = arr[j]
        arr[j] = arr[min]
        arr[min] = temp
    }
    return arr
}

实现

从大到小

var arr = [32, 14, 6, 9, 20, 58];
// var arr = [3, 3, 1, 1]

// 循环次数：(arr.length*arr.length-1)/2
// arr.length-1+arr.length-2+arr.length-3...
// 5+4+3+2+1
// 第一轮内层循环arr.length - 1 - 0次，即5次
// 第二轮内层循环arr.length - 1 - 1次，即4次
// 第三轮内层循环arr.length - 1 - 2次，即3次
// 第四轮内层循环arr.length - 1 - 3次，即2次
// 第五轮内层循环arr.length - 1 - 5次，即1次
// 第六轮内层循环arr.length - 1 - 6次，即0次
function selectionSort(arr) {
    for (var j = 0; j < arr.length; j++) {
        // 记录最小值的下标（且每次外层for循环重新修改查找范围(越来越小)）
        // 外层j=0，从j+1至到arr.length找最小值
        // 外层j=1，从j+2至到arr.length找最小值
        // ......
        var min = j

        // 内层循环，每次内层循环都找出最小值的下标
        // var i = min+1用处是每次都不和自己比较，
        // 比如第一次外循环j=0,min也等于0,如果var i=min，即arr[0] == arr[0],没必要比较
        // 比如第二次外循环j=1,min也等于1如果var i=min，即arr[1] == arr[1],没必要比较
        for (var i = min + 1; i < arr.length; i++) {
            console.log(1)
            // console.log(min, i)
            // 如果找到的值比最小值还小，则把min改成找到的值的下标
            if (arr[min] > arr[i]) {
                min = i
            }
        }
        // 将选择的j值和找到的最小值互换位置
        var temp = arr[j]
        arr[j] = arr[min]
        arr[min] = temp
    }
    return arr
}

从小到大

function selectionSort1(arr) {
    for (var j = 0; j < arr.length; j++) {
        var max = j
        for (var i = max + 1; i < arr.length; i++) {
            console.log(1)
            if (arr[max] < arr[i]) {
                max = i
            }
        }
        var temp = arr[j]
        arr[j] = arr[max]
        arr[max] = temp
    }
    return arr
}

冒泡排序

点这里：冒泡排序

插入排序

点这里：插入排序