排序算法:选择排序

前言

选择排序，作为经典的排序算法。与冒泡排序一样，在面试中也常常会被问到，如果你没有掌握，那面试也就结束了😅

本文采用图文的方式讲解选择排序的特点，分步骤讲解js的实现思路以及相对应的代码，欢迎各位感兴趣的开发者阅读本文😋

概念

从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换，重复这一操作的算法即选择排序。

特点

线性查找数组中的最小值
找到最小值后与序列中的比较值进行交换
交换完毕后1轮结束
新的一轮比较值的位置为当前轮数
重复上述操作，直至比较到序列的最后一个元素。

图解示例

如图所示，将下列数据按照从小到大的顺序进行排列。

用序列的1号元素与其之后的元素进行线性比较，找到最小值1。
将找到的最小值与序列的1号元素进行位置调换，1轮操作完成。
开始新一轮的比较，用序列的2号元素与其之后的元素进行线性比较，找到最小值2
将将找到的最小值与序列的2号元素进行位置调换。
重复上述操作，新一轮比较的元素位置为当前轮数，直至比较到序列的最后一个元素，则排序完成。

实现思路

声明一个函数，参数为一个数组
遍历数组，将数组中的值与其之后的元素进行比较，找到最小值
找到最小值后，将当前比较的值与最小值进行位置互换
直至遍历到最后一个元素，排序结束。

接下来，我们用JavaScript根据实现思路来实现下选择排序。

/**
 * 1. 从数组的0号元素开始和之后的元素进行大小比较
 * 2. 找到最小值后，将最小值与当前比较值进行位置互换
 * 3. 重复上述操作，当前轮数则为比较元素的位置，直至最后一轮的比较
 */

const selectSort = function (arr) {
    for (let i = 0; i < (arr.length-1); i++){
        // 最小值
        let min = arr[i];
        // 最小值位置
        let minIndex = i;
        // 比较次数
        let round = 0;
        for (let j = i+1; j<arr.length; j++){
            round ++;
            if(min>arr[j]){
                // 如果最小值大于当前比较值，则进最小值赋值当前遍历到的值
                min = arr[j];
                minIndex = j;
            }
        }
        console.log(`第${i+1}轮结束: ${arr},最小值${min},最小值位置${minIndex},共比较${round}次`);
        // 位置互换
        [arr[i],arr[minIndex]] = [min,arr[i]];
    }
    return arr;
};

const arrData = [4,6,7,8,9,1,2,3,4];
console.log(selectSort(arrData));

执行结果

写在最后

文中使用的图片源自《我的第一本算法书》，如若侵权，请评论区留言，作者立即删除相关图片。
文中如有错误，欢迎在评论区指正，如果这篇文章帮到了你，欢迎点赞和关注😊
本文首发于掘金，未经许可禁止转载💌