文章头图

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

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

算法介绍

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

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

算法图示:
第一轮排序

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

具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var swap = function(arr, posl, posr){
var m = arr[posl];
arr[posl] = arr[posr];
arr[posr] = m;
};
var simpleSelect = function(arr){
var len = arr.length;
var i, j, min;

for (i=0; i<len-1; i++) {
min = i;
for (j=i+1; j<len; j++) {
if (arr[min] > arr[j]) {
// 两两比较,将 Unicode 值更小的元素的下标保存到变量 min 中
min = j;
}
}
// 交换元素提取到此处,则交换次数将比冒泡排序的少
if (min !== i) {
swap(arr, i, min);
}
}

return arr;
};

复杂度分析

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

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

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

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