前言
虽然前端面试中很少会考到算法类的题目,但是你去大厂面试的时候就知道了,对基本算法的掌握对于从事计算机科学技术的我们来说,还是必不可少的,每天花上 10 分钟,了解一下基本算法概念以及前端的实现方式。
另外,掌握了一些基本的算法实现,对于我们日常开发来说,也是如虎添翼,能让我们的 js 业务逻辑更趋高效和流畅。
算法介绍
打个比方,喜欢短线炒股的朋友,习惯短时间内不断地买进卖出,通过价差来实现盈利。但是通常如此频繁操作,即使失误不多,也会因为操作的手续费和印花税而获利较少。另外一种长线炒股的朋友,习惯长时间持有,不断地观察和判断,时机一到便果断买进或卖出,交易次数少,收益颇丰。
上一节说的冒泡排序就类似于短线炒股,不断地比较之后进行交换,完成排序。而本节所要讲解的简单选择排序,类似于长线炒股,虽然也在不断地观察比较,但是会在合适的时机进行交换,并且只移动一次就完成相应关键字的排序定位工作。这就是选择排序法的初步思想。
算法图示:
具体实现指导:
假设数组中元素个数为
n
,则需要比较
n-1
轮,在第
i(1<=i<=n)
轮时,需要经过
n-i+1
次比较,选出
Unicode
码最小的元素,并在本轮结束后与第
i
个元素进行交换,当然了,若第
i
个元素本来就是最小的,就不用进行交换了。注:约定第 1 个元素的下标为 0。
具体实现
var swap = function(arr, posl, posr){
var m = arr[posl];
arr[posl] = arr[posr];
arr[posr] = m;
};
var simpleSelect = function(arr