文章头图

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

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

算法介绍

归并排序(英语:Merge sort,或mergesort),是创建在归并操作上的一种有效的排序算法。1945 年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。——维基百科

归并操作(Merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

归并操作示意图

归并操作示意图(维基百科)

算法阐述

归并排序就是利用归并的思想实现的排序方法。它的原理是假设初始数组含有 n 个元素,则可以看成是 n 个有序的子数组,每个子数组的长度为 1,然后两两归并,得到 Ceil(n/2) 个长度为 21 的有序数组;再两两归并,如此重复,直至得到一个长度为 n 的有序序列为止。

这种排序方法称为「2 路归并排序」。

以数组 arr = [6, 5, 3, 1, 8, 7, 2, 4] 为例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
   [6, 5, 3, 1, 8, 7, 2, 4]

[6] [5] [3] [1] [8] [7] [2] [4]
↓ ↓ ↓ ↓
[6, 5] [3, 1] [8, 7] [2, 4]
↓ ↓ ↓ ↓
[5, 6] [1, 3] [7, 8] [2, 4]
↓ ↓
[5, 6, 1, 3] [7, 8, 2, 4]
↓ ↓
[1, 3, 5, 6] [2, 4, 7, 8]

[1, 3, 5, 6, 2, 4, 7, 8]

[1, 2, 3, 4, 5, 6, 7, 8]

排序过程的动画演示图:
排序过程的动画演示图

排序过程的动画演示图(维基百科)

具体实现:利用递归方式

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
var RecurseMergeSort = function(arr){
MSort(arr, arr, 0, arr.length-1);
};
var MSort = function(sArr, tArr, s, t){
var m;
var tmpArr = [];

if (s === t) {
// 如果只剩一个元素
tArr[s] = sArr[s];
} else {
// 分割数组
m = Math.floor((s+t)/2);
MSort(sArr, tmpArr, s, m);
MSort(sArr, tmpArr, m+1, t);
// 归并数组
Merge(tmpArr, tArr, s, m, t);
}
};
var Merge = function(sArr, tArr, i, m, n){
var j=m+1, k=i, l;
for (; i<=m && j<=n; k++) {
if (sArr[i] < sArr[j]) {
tArr[k] = sArr[i];
i++;
} else {
tArr[k] = sArr[j];
j++;
}
}

// 将剩余的元素放入目标数组中
if (i <= m) {
for (l=i; l<=m; l++) {
tArr[k++] = sArr[l];
}
} else if (j <= n) {
for (l=j; l<=n; l++) {
tArr[k++] = sArr[l];
}
}
};

// 测试
var a = [2, 1, 3];
RecurseMergeSort(a);
console.log(a);

具体实现:利用迭代方式

「没有最好,只有更好」。

归并排序大量引用了递归,尽管在代码上比较清晰,容易理解,但这会造成时间和空间上的性能损耗。
我们排序追求的就是效率,因此将递归转化成迭代,进一步提高性能,来看代码。

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
28
29
var IterateMergeSort = function(arr){
var tempArr = [];
var k = 0;
while (k < arr.length-1) {
MergePass(arr, tempArr, k, arr.length);
k = 2*k+1;
MergePass(tempArr, arr, k, arr.length);
k = 2*k+1;
}
};

var MergePass = function(sArr, tArr, s, n){
var i = 0;
var j;
s += 1;
n -= 1;
while (i <= n-(2*s-1)) { // 即:i+(2*s-1) <= n
Merge(sArr, tArr, i, i+s-1, i+(2*s-1));
i = i+2*s;
}
// 归并最后两个数组
if (i < n-(s-1)) {
Merge(sArr, tArr, i, i+(s-1), n);
} else { // 最后只剩下单个数组
for (j=i; j<n; j++) {
tArr[j] = sArr[j];
}
}
};