阅读 125

排序算法:选择排序

前言

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

本文采用图文的方式讲解选择排序的特点,分步骤讲解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));
复制代码

执行结果

写在最后

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