搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 程序猿何大叔 > 浅解前端必须掌握的算法(二):简单选择排序

浅解前端必须掌握的算法(二):简单选择排序

程序猿何大叔 2018-07-01

前言

虽然前端面试中很少会考到算法类的题目,但是你去大厂面试的时候就知道了,对基本算法的掌握对于从事计算机科学技术的我们来说,还是必不可少的,每天花上 10 分钟,了解一下基本算法概念以及前端的实现方式。

另外,掌握了一些基本的算法实现,对于我们日常开发来说,也是如虎添翼,能让我们的 js 业务逻辑更趋高效和流畅。

算法介绍

打个比方,喜欢短线炒股的朋友,习惯短时间内不断地买进卖出,通过价差来实现盈利。但是通常如此频繁操作,即使失误不多,也会因为操作的手续费和印花税而获利较少。另外一种长线炒股的朋友,习惯长时间持有,不断地观察和判断,时机一到便果断买进或卖出,交易次数少,收益颇丰。

上一节说的冒泡排序就类似于短线炒股,不断地比较之后进行交换,完成排序。而本节所要讲解的简单选择排序,类似于长线炒股,虽然也在不断地观察比较,但是会在合适的时机进行交换,并且只移动一次就完成相应关键字的排序定位工作。这就是选择排序法的初步思想。

算法图示:

具体实现指导: 假设数组中元素个数为 n,则需要比较 n-1 轮,在第 i(1<=i<=n) 轮时,需要经过 n-i+1 次比较,选出 Unicode 码最小的元素,并在本轮结束后与第 i 个元素进行交换,当然了,若第 i 个元素本来就是最小的,就不用进行交换了。注:约定第 1 个元素的下标为 0。

具体实现

 
   
   
 
  1. var swap = function(arr, posl, posr){

  2.  var m = arr[posl];

  3.  arr[posl] = arr[posr];

  4.  arr[posr] = m;

  5. };

  6. var simpleSelect = function(arr){

  7.  var len = arr.length;

  8.  var i, j, min;

  9.  for (i=0; i<len-1; i++) {

  10.    min = i;

  11.    for (j=i+1; j<len; j++) {

  12.      if (arr[min] > arr[j]) {

  13.        // 两两比较,将 Unicode 值更小的元素的下标保存到变量 min 中

  14.        min = j;

  15.      }

  16.    }

  17.    // 交换元素提取到此处,则交换次数将比冒泡排序的少

  18.    if (min !== i) {

  19.      swap(arr, i, min);

  20.    }

  21.  }

  22.  return arr;

  23. };

复杂度分析

从以上过程来看,简单选择排序的最大特点就是交换元素的次数相当少,节约了相应的时间。当然数据量越大的时候,节约的时间约明显。

分析其时间复杂度发现,无论最好还是最坏的情况,其与冒泡排序的比较次数都是一样的,最坏情况下,时间复杂度如下:

但是对于交换次数而言,当最好的情况下,交换次数为 0,与冒泡排序的相同;最差的情况下,交换次数为 n-1次,比冒泡排序的 n(n-1)/2 次少了一个数量级。基于比较和交换次数的综合,可以得知,简单选择排序的时间复杂度依然为 O(n²)

尽管简单选择排序与冒泡排序的时间复杂度同为 O(n²),但简单选择排序在性能上还是略优于冒泡排序的。



觉得本文不错的话,分享一下给小伙伴吧~


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《浅解前端必须掌握的算法(二):简单选择排序》的版权归原作者「程序猿何大叔」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注程序猿何大叔微信公众号

程序猿何大叔微信公众号:hadestory

程序猿何大叔

手机扫描上方二维码即可关注程序猿何大叔微信公众号

程序猿何大叔最新文章

精品公众号随机推荐