专栏首页HTML5学堂算法之旅 | 选择排序法

算法之旅 | 选择排序法

HTML5学堂-码匠:数据快速的计算与排序,与前端页面性能有直接的关系。由于排序的算法有很多,在本次“算法系列”的分享当中,我们先从简单易上手的选择排序法开始,其它的排序算法会随后陆续跟大家一起分享。

算法的基本概念

算法是什么,它有何作用

为解决一个问题而采取的方法和步骤,称为算法。

我们可以把算法看成一本“福字剪纸教程”,其中每一种算法就是剪纸教程中的一种包含“固定步骤”的剪纸方法,使用者只要按照步骤进行剪纸,就可以剪出好看的福字。

之所以有这么多的算法,在于不同算法解决问题的效率各有不同,适合不同的场景。随着问题规模的增长,算法之间的差距会变的不可跨越。提升解决问题的效率,不仅仅依赖于选择快速的硬件,还依赖于选择有效(适合)的算法。

排序的使用场景

针对数组进行从大到小(或从小到大)的排序。例如:管理系统中按照成绩的排序,按阅读量对文章的排序等。

数据快速的计算与排序,与前端页面性能有直接的关系。(譬如在页面中有10000条的数据需要靠JS进行排序,采用不同的算法所消耗的时间差距甚大,直接影响着网站的用户体验)

常见的排序方法

较为常见的排序方法,包括:冒泡排序、选择排序、快速排序、二分法插入排序等。

由于排序的算法有很多,在本次“算法系列”的分享当中,我们先从简单易上手的选择排序法开始,其它的排序算法会随后陆续跟大家一起分享。

选择排序法的基本原理

先找到序列中最小的数,将它和序列中第一个数交换位置;

接下来,在剩下的序列中继续此操作:找到最小的数,将它和序列中的第二个数交换位置;

依此类推,直到将整个序列排序完成。

简言之,选择排序就是 —— 不断地选择剩余序列中的最小者,然后与未排序数列的“第一个”数字交换位置。

案例说明

如下数组中,黑色代表待排序,蓝色代表已排序;

初始状态:[9, 8, 3, 1, 2, 4]

第一次排序结果:[1, 8, 3, 9, 2, 4] 在剩余的序列中最小的数1,与第一个数交换位置;

第二次排序结果:[1, 2,3, 9, 8, 4] 在剩余的序列中最小的数2,与第二个数交换位置;

第三次排序结果:[1, 2, 3, 9, 8, 4] 在剩余的序列中最小的数3,自己本身,所以位置不变;

第四次排序结果:[1, 2, 3, 4, 8, 9] 在剩余的序列中最小的数4,与第四个数交换位置;

第五次排序结果:[1, 2, 3, 4, 8, 9] 在剩余的序列中最小的数8,自己本身,所以位置不变;

最后一个数已经是最大的数,不需要再次排序。

实现选择排序的步骤分解

排序次数

排序次数:序列长度 – 1(注意,不是比较次数);

因为序列中的最后一个数不需要再次比较大小,故排序次数为 序列长度 – 1。

找到最小的数

序列中找到最小的数,并记录该数的索引值;

因为minIndex默认开始为0,则第一个数无需与自身比较,所以j = i + 1;

// 遍历序列,找到最小的数
for (var j = i + 1; j < len; j++) {
    if (arr[j] < arr[minIndex]) {

        // 记录最小数的索引
        minIndex = j;
    };
};

在排序次数内多次遍历找到最小的数,因此需要再用一个for语句来进行控制。

// 排序次数
for (var i =   0; i < len - 1; i++) {
    // 默认最小数的索引为i
    minIndex = i;
    // 遍历序列,找到最小的数
    for (var j = i + 1; j < len; j++) {
        if (arr[j] < arr[minIndex]) {
            // 记录最小数的索引
            minIndex = j;
        };
    };
};

两数交换位置

利用temp变量,实现两数组元素之间数值的交换,也就是交互位置。

temp =   arr[i];
arr[i] =   arr[minIndex];
arr[minIndex]   = temp;
选择排序法完整代码
var arr = [9, 8, 3, 1, 2, 4],
    len = arr.length,
    minIndex, temp;
    // 排序次数
    for (var i =   0; i < len - 1; i++) {
        // 默认最小数的索引为i
        minIndex = i;
        // 遍历剩下的序列,找到最小的数
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                // 记录最小数的索引
                minIndex = j;
            };
        };
    // HTML5学堂出品
    // 两数交互位置
    temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
};
console.log(arr);

选择排序法的效率

算法复杂度的基本概念

算法复杂度分为时间复杂度和空间复杂度(时间和空间是计算机最重要的资源,因此复杂度分为时间和空间)。

时间复杂度:指执行算法所需要的计算工作量;

空间复杂度:指执行算法所需要的内存空间。

时间复杂度:O(n*n)

时间复杂度是总运算次数表达式中受n的变化影响最大的项(不含系数);

第一次循环比较n-1次,然后是n-2次,n-3次,依此类推,最后一次循环比较1次,总的比较次数和为(n - 1 + 1) * n / 2,即进行比较操作的时间复杂度为O(n^2)

Tips:选择排序的比较次数与序列的初始排序无关。

空间复杂度:O(1)

排序算法需要一个额外的空间(temp变量)来交换元素的位置。

不稳定排序的一种算法

选择排序是一种不稳定排序的算法。

比如:序列[3, 8, 3, 1, 9 ],第一次循环第1个元素3会和1交换,变成[1, 8, 3, 3, 9],此时,原序列中两个3的先后顺序被破坏

本文分享自微信公众号 - HTML5学堂(h5course-com),作者:HTML5学堂(码匠)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-08-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法之旅 | 冒泡排序法

    HTML5学堂-码匠:本期继续走入算法 —— 冒泡排序法。冒泡排序算法相对简单,容易上手,稳定性也比较高, 算是一种较好理解的算法,也是面试官高频提问的算法之一...

    HTML5学堂
  • 网络字体@font-face 如何处理网页中的特殊字体

    HTML5学堂:随着网页的发展,网页中出现了越来越多的字体种类,网页自带的微软雅黑、宋体、黑体已经越来越难以满足设计的需要,那么,如何在网站中使用比较特殊的字体...

    HTML5学堂
  • 算法之旅 | 快速排序法

    HTML5学堂-码匠:前几期“算法之旅”跟大家分享了冒泡排序法和选择排序法,它们都属于时间复杂度为O(n^2)的“慢”排序。今天跟大家分享多种排序算法里使用较广...

    HTML5学堂
  • 算法之旅 | 冒泡排序法

    HTML5学堂-码匠:本期继续走入算法 —— 冒泡排序法。冒泡排序算法相对简单,容易上手,稳定性也比较高, 算是一种较好理解的算法,也是面试官高频提问的算法之一...

    HTML5学堂
  • 算法| 选择排序

    第一步要找到其中的最小值将其放到第一个位置,然后找余下的最小值放到第二个位置,以此类推。

    fem178
  • 各大排序算法性能比较及演示实例

    所谓排序,即将原来无序的一个序列重新排列成有序的序列。 排序方法中涉及到稳定性,所谓稳定性,是指待排序的序列中有两个或两个以上相同的项,在排序前和排序后看这些相...

    顶级程序员
  • 交易所纷纷支持挖矿,谁主沉浮?

    随着六月初,FCoin开创了交易挖矿的新纪元之后,挖矿正式进入了交易所和普通用户的视野。所有人都不觉眼前一亮,原来交易所还可以这么玩?而随着以FCoin为首的挖...

    区块链领域
  • 编程有感,Web 新时代的机遇与挑战

    技术决定了业务需求的多样性,而业务需求的多样性又推动着技术不断向前发展,两者相辅相成最终才能推动行业整体的发展和进步。

    用户5997198
  • 好用的函数,assert,random.

       random.sample的函数原型为:random.sample(sequence, k),从指定序列中随机获取指定长度的片断。sample函数不会修改...

    py3study
  • 推荐系统常用算法总结(适合刚入门的同学)

    从推荐算法的理论来讲,主要可以从召回层和排序层两个方面来说,虽然召回层和排序层都是使用算法和模型来做,但是针对于不用的阶段,所用的模型也有一定的差...

    黄鸿波

扫码关注云+社区

领取腾讯云代金券