一、 前言

在以往的工作经验中,数据结构和算法对于很多前端工程师来说,一直是可有可无的。但个人觉得,前端工程师其实也是需要重视数据结构和算法的,因为前端所做的东西是用户访问网站第一眼看到的东西,特别在移动浪潮到来之后,对用户体验越来越高,对前端提出了更高的要求,面对越来越复杂的产品,需要坚实的数据结构和算法基础才能驾驭。

如果没有学习过计算机科学的程序员,当我们在处理一些问题时,比较熟悉的数据结构就是数组,数组无疑是一个很好的选择。但很多时候,对于很多复杂的问题,数组就显得太过简陋了,当学习了数据结构和算法之后,对于很多编程问题,当想到一个合适的数据结构后,设计和实现解决这些问题的算法就手到擒来。

  • 数据结构:列表、栈、队列、链表、字典、散列、图和二叉查找树
  • 排序算法:冒泡排序、选择排序、插入排序、希尔排序、归并排序和快速排序
  • 查找算法:顺序查找和二分查找

二、 数据结构

1. 列表

在日常生活中,人们经常使用列表:待办事项列表、购物清单、最佳十名榜单等等。
而计算机程序也在使用列表,它是一组有序的数据,每个列表中的数据项称为元素。在JS中,列表中的元素可以是任意数据类型。列表中可以保存多少元素并没有限定(在实际使用时会受到程序内存的限制)。

列表的数据结构较为简单,不需要在一个长序列中查找元素,或者对其进行排序。反之,如果数据结构非常复杂,列表的作用就没有那么大了。


2. 栈

Stack是一种 LIFO (Last-In-First-Out) 后进先出的数据结构,是一种特殊的列表。想象一下,我们平常在饭馆见到的一摞盘子就是现实世界常见的栈的例子,只能从最上面取盘子,盘子洗干净后,也只能放在最上面。

栈是一种高效的数据结构,因为栈内的元素只能通过列表的一端访问,这一端称为栈顶。只要数据的保存满足后入先出或先进后出的原理,都优先考虑使用栈。


3. 队列

队列Queue是典型的 FIFO (First-In-First-Out) 先进先出的数据结构,也是一种特殊的列表,不同的是队列只能在队尾插入元素,在队首删除元素。想象一下,我们在银行排队,排在最前面的人第一个办理业务,而后面来的人只能排在队伍的后面,直到轮到他们为止。

  • 消息机制可以通过队列来实现,进程调度也是使用队列来实现。

只要数据的保存满足先进先出、后入后出的原理,都优先考虑使用队列。


4. 链表

链表LinkedList也是一种列表,与其他语言(比如C++和Java)的数组相比,在JavaScript中数组被实现成了对象,数组的索引下标需要在js语言内部转换为js对象的属性名,因此效率很低。如果你发现数组在实际使用时很慢,就可以考虑使用链表来代替它。

  • 单链表中的每个结点不仅包含值,还包含链接到下一个结点的引用字段。通过这种方式,单链表将所有结点按顺序组织起来。

  • 双链表以类似的方式工作,但还有一个引用字段,称为“prev”字段。有了这个额外的字段,您就能够知道当前结点的前一个结点。

  • 循环链表 和单链表相似,节点类型都是一样,唯一的区别是,在创建循环链表的时候,让其头节点的 next 属性执行它本身。

在实际应用中,除了有随机访问的需求之外,其他情况都可以用链表替换数组。


5. 字典

字典Dictionary是一种以键-值对存储数据的数据结构,JavaScript中的Object类就是以字典的形式设计的。JavaScript可以通过实现字典类,让这种字典类型的对象使用起来更加简单,字典可以实现对象拥有的常见功能,并相应拓展自己想要的功能。

对象在JavaScript编写中随处可见,所以字典的作用也异常明显了。


6. 散列

散列Hash(也称为哈希表)是一种的常用的数组存储技术,散列后的数组可以快速地插入或取用。散列使用的数据结构叫做散列表。在散列表上插入、删除和取用数据都非常快,但对于查找操作来说却效率低下,比如查找一组数组中的最大值和最小值。这些操作需要求助于其他数据结构,比如二叉查找树。

散列表在JavaScript中可以基础数组去进行设计。数组的长度是预先设定的,所有元素根据和该元素对应的键,保存在数组的特定位置,这里的键和对象的键是类型的概念。使用散列表存储数组时,通过一个散列函数将键映射为一个数字,这个数字的范围是0到散列表的长度。

  • 哈希表的关键思想是使用哈希函数将键映射到存储桶

即使使用一个高效的散列函数,依然存在将两个键映射为同一个值得可能,这种现象叫做碰撞。常见碰撞的处理方法有:开链法和线性探测法。

哈希表可以用于数据的插入、删除和取用,不适用于查找数据。


7. 图

Graph由边的集合及顶点的集合组成。 顶点代表对象,边则建立起对象之间的关系或关联。
如果一个图的顶点对是有序的,则称之为有向图(如流程图),反之,称之为无序图。

  • 图的存储结构一般为邻接矩阵和邻接表。
  • 搜索图的算法主要有两种:深度优先搜索和广度优先搜索。


8. 二叉树

Tree一种非线性的数据结构,以分层的方式存储数据。
在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点,简称树的(root)。每一个结点可以有多个后件,称为该结点的子结点。没有后件的结点称为叶子结点。一个结点所拥有的子结点的个数称为该结点的度,所有结点中最大的度称为树的度。树的最大层次称为树的深度。

二叉树每个节点的子节点不允许超过两个。一个父节点的两个子节点分别称为左节点和右节点,通过将子节点的个数限定为2,可以写出高效的程序在树中插入、查找和删除数据。

按照根节点访问的顺序不同,树的遍历分为以下三种:

  • 前序遍历:根节点->左子树->右子树 ABDEFGC
  • 中序遍历:左子树->根节点->右子树 DEBGFAC
  • 后序遍历:左子树->右子树->根节点 EDGFBCA

二叉查找树BST(Binary Sort Tree)是一种特殊的二叉树,相对较小的值保存在左节点中,较大的值保存在右节点中。这一特性使得查找的效率很高,对于数值型和非数值型的数据,比如单词和字符串,都是如此。

由于树存储的所有元素之间具有明显的层次特性,因此常被用来存储具有层级关系的数据,比如文件系统中的文件;也会被用来存储有序列表等。


三、 排序算法

普通排序算法

普通排序算法基本核心思想是指对一组数组按照一定的顺序重新排列。重新排列时用到的技术是一组嵌套的for循环。其中外循环会遍历数组的每一项,内循环则用于比较元素。

1. 冒泡排序

冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

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
// 基础版
function bubbleSort (arr) {
let i = 0, j = 0
for (i; i < arr.length - 1; i++) {
for (j; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp;
}
}
}
return arr
}
// 优化版
function bubbleSort (arr) {
let i = arr.length
while (i > 0) {
let pos = 0, j = 0
for (j; j < i; j++) {
if (arr[j] > arr[j+1]){
pos = j
let temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
}
}
i = pos
}
return arr
}
let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
bubbleSort(arr)
// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]


2. 选择排序

选择排序 (Selection Sort) 是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function selectionSort (arr) {
let len = arr.length;
let minIndex, temp;
for (let i = 0; i < len - 1; i++) {
minIndex = i;
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j
}
}
temp = arr[minIndex]
arr[minIndex] = arr[i]
arr[i] = temp
}
return arr
}

let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];

console.log(selectionSort(arr));
//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]


3. 插入排序

插入排序(Insertion Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function insertSort (arr) {
let len = arr.length
for (i = 1; i < len; i++) {
let key = arr[i]
let j = i - 1
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]
j--;
}
arr[j + 1] = key
}
return arr
}
let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(insertSort(arr));
//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]


高级排序算法

高级数据排序算法,通常用于处理大型数据集的最高效排序算法,它们处理的数据集可以达到上百万个元素,而不仅仅是几百个或者几千个,下面我们将介绍希尔排序、归并排序和快速排序。

4. 希尔排序

1959年Shell(Shell Sort)发明,第一个突破O(n^2)的排序算法;是简单插入排序的改进版;它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列,也可以动态的定义间隔序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function shellSort (arr) {
let len = arr.length;
let temp, gap = 1;
while (gap < len / 3) {
gap = gap * 3 + 1
}
while (gap >= 1) {
for (let i = gap; i < len; i++) {
temp = arr[i]
for (let j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
arr[j + gap] = arr[j]
}
arr[j + gap] = temp
}
gap = (gap - 1) / 3
}
return arr
}
let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(shellSort(arr));
//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]


5. 归并排序

归并排序(Merge Sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

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
function mergeSort (arr) {
let len = arr.length
if (len < 2) {
return arr
}
let middle = Math.floor(len / 2)
let left = arr.slice(0, middle)
let right = arr.slice(middle)
return merge(mergeSort(left), mergeSort(right));
}
function merge (left, right) {
let result = []
while (left.length && right.length) {
if (left[0] < right[0]) {
result.push(left.shift())
} else {
result.push(right.shift())
}
}
while (left.length) {
result.push(left.shift())
}
while (right.length) {
result.push(right.shift())
}
return result
}
let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(mergeSort(arr));



6. 快速排序

快速排序(Quick Sort)是处理大数据集最快的排序算法之一。

它是一种分而治之的算法,通过递归的方法将数据依次分解为包含较小元素和较大元素的不同子序列。该算法不断重复这个步骤知道所有数据都是有序的。
这个算法首先要在列表中选择一个元素作为基准值。数据排序围绕基准值进行,将列表中小于基准值的元素移到数组的底部,将大于基准值的元素移到数组的顶部。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function qSort (arr) {
if (arr.length == 0) {
return []
}
let left = []
let right = []
let pivot = arr[0]
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return qSort(left).concat(pivot, qSort(right))
}
let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(qSort(arr));


四、 查找算法

在列表中查找数据有两种方式:顺序查找二分查找。顺序查找适用于元素随机排列的列表;二分查找适用于元素已排序的列表。二分查找效率更高,但是必须在进行查找之前花费额外的时间将列表中的元素排序。

1. 顺序查找

对于查找数据,最简单的方法就是从列表的第一个元素开始对列表元素逐个进行判断,直到找到了想要的结果,或者直到列表结尾也没有找到。这种方法称为顺序查找,有时也被称为线性查找。

1
2
3
4
5
6
7
8
9
10
function seqSearch (arr, data) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === data) {
return i;
}
}
return -1;
}
let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(seqSearch(arr, 15))


2. 二分查找

二分法查找,也称折半查找,是一种在有序数组中查找特定元素的搜索算法。

查找过程可以分为以下步骤:
首先,从有序数组的中间的元素开始搜索,如果该元素正好是目标元素(即要查找的元素),则搜索过程结束,否则进行下一步。
如果目标元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半区域查找,然后重复第一步的操作。
如果某一步数组为空,则表示找不到目标元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function binSearch (arr, data) {
let low = 0;
let high = arr.length - 1
while (low <= high) {
let middle = Math.floor((low + high) / 2)
if (arr[middle] < data) {
low = middle + 1
} else if (arr[middle] > data) {
high = middle - 1
} else {
return middle
}
}
return -1
}
let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(binSearch(arr, 15))


参考文章: