文章头图

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

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

算法介绍

冒泡排序很简单,就是数组中的相邻元素,两两比较,数值或者 Unicode 码小的元素往前排。

冒泡算法排序图

具体实现指导如下:

  1. 比较相邻两个元素,若前一个比后一个大,则交换位置;
  2. 第一轮结束之后,最后一个元素的值是最大的;
  3. 接着开始第二轮,但是不用再比较最后一个元素了;
  4. 第一轮除外,以后的每一轮都比前一轮少比较一次;

具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var bubbleSort = function (arr){
var i, j, m;
var len = arr.length;
if (len <= 1) {
return arr;
}

for (i=0; i<len-1; i++) {
for (j=0; j<len-i-1; j++) {
if (arr[j] > arr[j+1]) {
m = arr[j];
arr[j] = arr[j+1];
arr[j+1] = m;
}
}
}
return arr;
};

算法改进

如果数组原本的顺序就是冒泡的,又或者仅做完前面寥寥几次就已经达到效果了,那后续的比较工作就显得有些多余了,如何对以上算法进行改进?

我们可以在某一轮的循环比较结束后,如果没有发生任何的元素交换,则可以认为该数组已经达到预期效果,不必再继续下一轮的比较了。

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
26
27
var bubbleSort = function (arr){
var start = +new Date();
var i, j, m, noswap;
var len = arr.length;
if (len <= 1) {
return arr;
}

for (i=0; i<len-1; i++) {
noswap = true;
for (j=0; j<len-i-1; j++) {
if (arr[j] > arr[j+1]) {
m = arr[j];
arr[j] = arr[j+1];
arr[j+1] = m;
noswap = false;
}
}
if (noswap) {
break;
}
}

// 当 arr 的长度越长,时间差越明显
console.log(+new Date() - start);
return arr;
};

时间度复杂度分析

分析时间复杂度就按最坏的情况来,即待排序表是完全逆序的情况。
假设数组中共有 n 个元素,第一轮需要比较 n-1 次,第二轮需要比较 n-2 次,第三轮需要比较 n-3 次,以此类推,最后一轮需要比较 1 次,共比较 n-1 轮,所以是个等差数列,运用等差数列求和公式,能计算出如下时间复杂度:

因此总的时间复杂度为 O(n²)