选择排序

前端 0 347 0
发表于: 2021-02-18 19:00:19

简介: 暂无~

选择排序

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

基本原理

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

比如,第一次排序,所有元素(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
}

冒泡排序

点这里:冒泡排序

插入排序

点这里:插入排序

数据结构和算法

最后更新于:2021-02-19 03:33:38

欢迎评论留言~
0/400
支持markdown
Comments | 0 条留言
按时间
按热度
目前还没有人留言~