JavaScript 数据结构与算法

发表于 | 分类于 | 阅读次数

栈

先进后出，采用数组实现。利用数组的 push 和 pop 方法实现入栈、出栈的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
class Stack () {
  constructor () {
    this.items = []
  }
  push (item) {
    this.items.push(item)
  }
  pop () {
    return this.items.pop()
  }
}

队列

先进先出，采用数组实现，与栈结构很相似，只是添加和删除元素的位置不同。主要是利用数组的 push 和 shift 方法实现入队、出队的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Queue () {
  constructor () {
    this.items = []
  }
  enqueue (item) {
    this.items.push(item)
  }
  dequeue () {
    return this.items.shift()
  }
  size () {
    return this.items.length
  }
}

优先队列

可以设置两种优先级：添加优先级、删除优先级

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
class Queue () {
  constructor () {
    this.items = []
  }
  enqueue (elem, priority) {
    var self = this
    var queueElem = {
      elem,
      priority
    }
    if (self.isEmpty()) {
      self.items.push(queueElem)
    } else {
      let added = false
      
      for (let i = 0, len = self.items.length; i < len; i++) {
        if (queueElem.priority < self.items[i].priority) {
          self.items.splice(i, 0, queueElem)
          added = true
          break
        }
      }
      if (!added) {
        self.items.push(queueElem)
      }
    }
    
  }
  dequeue () {
    return this.items.shift()
  }
  isEmpty () {
    return this.items.length === 0
  }
}

循环队列——击鼓传花

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function hotPotato (nameList, num) {
  var queue = new Queue()
  for (let i = 0, len = nameList.length; i < len; i++) {
    queue.enqueue(nameList[i])
  }
  let eliminated = ''
  while (queue.size() > 1) {
    for (let j = 0; j < num; j++) {
      queue.enqueue(queue.dequeue())
    }
    eliminated = queue.dequeue()
    console.log(eliminated + '在击鼓传花游戏中被淘汰')
  }
  return queue.dequeue()
}

链表

采用对象来实现链表中的元素

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class LinkedList () {
  constructor (elem) {
    this.node = {
      elem,       // 当前节点
      next: null  // 下一个节点的指针
    }
    this.head = null
    this.length = 0
  }
  append (element) {
    this.node.elem = element
    let node = this.node
    if (head === null) {
      head = node
    } else {
      current = head
      while (current.next) {
        current = current.next
      }
      current.next = node
    }
    this.length++
  }
  removeAt (pos) {
    if (pos > -1 && pos < this.length) {
      let current = head, previous, index = 0
      if (pos === 0) {
        head = current.next
      } else {
        while (index++ < pos) {
          previous = current
          current = current.next
        }
        previous.next = current.next
      }
      this.length--
      return current.elem
    } else {
      return null
    }
  }
  insert (pos, elem) {
    if (pos >= 0 && pos <= this.length) {
      let current = head, previous, index = 0
        
      this.node.elem = elem
      if (pos === 0) {
        this.node.next = current
        head = this.node
      } else {
        while (index++ < pos) {
          previous = current
          current = current.next
        }
        this.node.next = current
        previous.next = this.node
      }
      this.length++
      return true
    } else {
      return false
    }
  }
}

双向链表

链表的节点中有两个指针，一个指向前一个节点，另一个指向后一个节点

1
2
3
4
5
var Node = function (elem) {
  this.elem = elem
  this.prev = null
  this.next = null
}

集合（Set）

ES6 已原生支持 Set 类型，表示一组互不相同的元素（不重复的元素）。采用对象进行模拟集合结构

字典（Map）

字典也是存储互不相同的元素，但是存储的是键值对。ES6 已原生支持 Map 类型。采用对象进行模拟字典结构

树

树是一种分层数据的抽象模型。树包含了一系列存在父子关系的节点。每个节点（除了根节点）都有一个父节点以及零个或多个子节点

二叉树

二叉树中的节点最多只有两个子节点：左侧节点和右侧节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var Node = {
  left: null,
  right: null,
  data: ''
}
// 遍历
function travelTree (node) {
  if (node) {
    console.log(node.data)
    travelTree(node.left)
    travelTree(node.right)
  }
}

二叉搜索树

二叉搜索树只允许左侧节点存储（比父元素）小的值，右侧节点存储（比父元素）大（或者相等）的值

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
class BinarySearchTree() {
  constructor (key) {
    this.node = {
      key,
      left: null,
      right: null
    }
    this.root = null
  }
  insert (node, newNode) {
    if (node.key < newNode.key) {
      if (node.left === null) {
        node.left = newNode
      } else {
        this.insert(node.left, newNode)
      }
    } else {
      if (node.right === null) {
        node.right = newNode
      } else {
        this.insert(node.right, newNode)
      }
    }
  }
}

二叉搜索树查找最小值，只需要遍历树的左节点就行；同理，查找最大值，只需遍历树的右节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function minNode (node) {
  if (node) {
    while (node && node.left !== null) {
      node = node.left
    }
    return node.key
  }
}
function maxNode (node) {
  if (node) {
    while (node && node.right !== null) {
      node = node.right
    }
    
    return node.key
  }
}

图

图是网络结构的抽象模型。图是一组由边连接的节点(或顶点)。
一个图G = (V, E)由以下元素组成。

V: 一组顶点
E: 一组边，连接V中的顶点

基本术语

由一条边连接在一起的顶点称为相邻顶点。
一个顶点的度是其相邻顶点的数量
路径是顶点v1, v2,…,vk的一个连续序列，其中vi和vi+1是相邻的
简单路径要求不包含重复的顶点
如果图中不存在环，则称该图是无环的。如果图中每两个顶点间都存在路径，则该图是连通的
图可以是无向的(边没有方向)或是有向的(有向图)
如果图中每两个顶点间在双向上都存在路径，则该图是强连通的

图的遍历

广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻点，就像一次访问图的一层。换句话说，就是先宽后深地访问顶点。

采用队列实现，通过将顶点存入队列中，最先入队列的顶点先被探索

深度优先搜索算法将会从第一个指定的顶点开始遍历图，沿着路径直到这条路径最后一个顶点被访问了，接着原路回退并探索下一条路径。换句话说，它是先深度后广度地访问顶点

采用栈实现，通过将顶点存入栈中，顶点是沿着路径被探索的，存在新的相邻顶点就去访问

排序算法

冒泡排序（复杂度 O(n^2)）

冒泡排序比较任何两个相邻的项，如果第一个比第二个大，则交换它们，元素项向上移动至正确的顺序，就好像气泡升至表面一样，冒泡排序因此得名。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function bubbleSort (array) {
  var len = array.length
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len -1; j++) {
      if (array[j] > array[j + 1]) {
        swap (j, j + 1)
      }
    }
  }
}
function swap (index1, index2) {
  return [array[index1], array[index2]] = [array[index2], array[index1]]
}

采用双重循环进行数组遍历，外循环控制在数组中进行了多少次的排序

改进后的冒泡排序

1
2
3
4
5
6
7
8
9
10
function modifiedBubbleSort (array) {
  var len = array.length
  for (let i = 0; i < len; i++) {
    for (let j=0; j < len - 1 - i; j++ ){
      if (array[j] > array[j + 1]) {
        swap (j, j + 1)
      }
    } 
  }
}

如果从内循环减去外循环中已跑过的轮数，就可以避免内循环中所有不必要的比较

选择排序（复杂度 O(n^2)）

选择排序算法是一种原址比较排序算法。选择排序大致的思路是找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function selectSort (array) {
  let len = array.length, indexMin
  for (let i = 0; i < len - 1; i++) {
    indexMin = i
    for (let j = i; j < len; j++) {
      if (array[indexMin] > array[j]) {
        indexMin = j
      }
    }
    if (i !== indexMin) {
      swap(i, indexMin)
    }
  } 
}

插入排序（复杂度O(n^2）

插入排序每次排一个数组项，以此方式构建最后的排序数组。假定第一项已经排序了，接着，它和第二项进行比较，第二项是应该待在原位还是插到第一项之前呢?这样，头两项就已正确排序，接着和第三项比较(它是该插入到第一、第二还是第三的位置呢?)，以此类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function insetSort (array) {
  let len = array.length, j, temp
  
  for (let i = 1; i < len; i++) {
    j = i
    temp = array[i]
    while (j > 0 && array[j - 1] > temp) {
      array[j] = array[j - 1]
      j--
    }
    array[j] = temp
  }
}

排序小型数组时，此算法比选择排序和冒泡排序性能要好。

归并排序（复杂度 O(nlogn)）

归并排序是一种分治算法，其思想是将原始数组切分成较小的数组，直到每个小数组只有一 个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。采用递归实现

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
function mergeSort (array) {
  array = mergeSortRec(array)
}
function mergeSortRec (array) {
  let len = array.length
  if (len === 1) {
    return array
  }
  let mid = Math.floor(len / 2),
    left = array.splice(0, mid),
    right = array.splice(mid, len)
  return merge(mergeSortRec(left), mergeSortRec(right))
}
function merge (left, right) {
  let result = [],
    il = 0,
    ir = 0
  let leftLen = left.length,
    rightLen = right.length
  while (il < leftLen && ir < rightLen) {
    if (left[il] < right[ir]) {
      result.push(left[il++])
    } else {
      result.push(left[ir++])
    }
  }
  while (il < leftLen) {
    result.push(left[il++])
  }
  while (il < rightLen) {
    result.push(left[ir++])
  }
  return result
}

快速排序（复杂度 O(nlogn)）

快速排序也是分治的思想，将原始数组分为较小的数组。基本思想是找一个基准值，根据这个基准值将一个数组分成两个子数组，逐渐递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function quickSort (array) {
  let len = array.length,
    pivotIndex = Math.floor( len / 2)
    pivot = array.splice(pivotIndex, 1)[0]
  let left = [], right = []
  if (len <= 1) {
    return 
  }
  arr.forEach((item) => {
    if (item < qivot) {
      left.push(item)
    } else {
      right.push(item)
    }
  })
  return quickSort(left).concat([qivot], quickSort(right))
}

以上快排算法主要是学习阮一峰老师早期的一篇博文，最近（2018年五月）这个快排算法在知乎上被吐槽了，连带阮一峰老师也被 diss 了。我想说的是，虽然这个算法的空间复杂度和时间复杂度确实不怎样，阮一峰老师这个快排的思想没错，而且对于新人来讲，这个快排算法通俗易懂，在此感谢阮一峰老师，在业内输出了大量的博文（http://www.ruanyifeng.com/blog/），让我们学到了更多。通过此事，其实我们更应该反思，对于现有的知识，我们不能够直接拿来就学，对于知识自己要多实践、多思考。

空间复杂度和时间复杂度更优的快排算法

基本思想：选取数组中一项作为主元，然后创建左右两个指针，分别从数组头部和尾部开始向中间进行遍历。移动左指针，直到找到一个比主元大的元素，接着移动右指针，找到一个比主元小的元素，然后交换这两个元素。重复这个过程，直至左指针超过了右指针，主元左边的元素都比主元小，右边的元素都比主元大。这一操作称为划分

接着对划分后的数组再递归进行划分，直至数组排好序。

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
48
49
50
function quickSort () {
  return quick(arr, 0, arr.length - 1)
}
function quick (arr, left, right) {
  let index
  
  if (arr.length > 1) {
  	index = partition(arr, left, right)
  	
  	if (left < index -1) {
  	  quick(arr, left, index -1)
  	}
  	
  	if (index < right) {
  	  quick(arr, index, right)
  	}
  }
}
// 划分数组
function partition (arr, left, right) {
  let pivot = arr[Math.floor((left + right)/2)]
  let i = left, j = right
  
  while (i <= j) {
    while (arr[i] < pivot) {
    	i++
    }
    
    while (arr[j] > pivot) {
    	j--
    }
    
    if (i <= j) {
    	swap(arr, i, j)
    	i++
    	j--
    }
  }
  
  return i
}
// 交换数组元素
function swap (arr, i, j) {
  let temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

搜索算法

顺序（线性）搜索

将每一个数据结构中的元素和我们要找的元素做比较，这是最低效的一种搜索算法。
具体实现略

二分搜索

二分搜索，首先要求被搜索的数据结构已排序，然后选取中间值，判断中间值与搜索值的关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function binarySearch (item) {
  quickSort() // 对数组进行排序
  let low = 0,
    high = array.length - 1,
    mid,  elem
  while (low <= high) {
    mid = Math.floor((low + high) / 2)
    if (array[mid] < item) {
      low = mid + 1
    } else if (array[mid] > item) {
      high = mid - 1
    } else {
      return mid
    }
  }
  return -1
}

其余算法

递归

递归是一种解决问题的方法，它解决问题的各个小部分，直到解决最初的大问题。通常涉及函数调用自身。
每个递归函数都必须要有边界条件，即一个不再递归调用的条件(停止点)， 以防止无限递归。

实例：斐波那契数列

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
// 递归实现
function fib (num) {
  if (num == 1 || num == 2) {
    return 1
  }
  return fibonacci(num - 1) + fibonacci(num - 2)
}
// 非递归实现
function fib (num) {
  let n1 = 1, n2 = 2, n = 1
  for (let i = 3; i <= num; i++) {
    n = n1 + n2
    n1 = n2
    n2 = n
  }
  return n
}
// ES6 generator 实现
function* fib (num) {
  let [a, b] = [0, 1]
  
  while (true) {
    [a, b] = [b, a + b]
    yield a
  }
}
for (let n of fib()) {
  if (n > 1000) break
  console.log(n)
}

动态规划

动态规划(Dynamic Programming，DP)是一种将复杂问题分解成更小的子问题来解决的优化技术。
与分治思想有所不同，分治思想是将问题分解成相互独立的子问题，然后组合它们的答案；动态规划则是将问题分解成相互依赖的子问题。
用动态规划解决问题时，要遵循三个重要步骤：

定义子问题
实现要反复执行而解决子问题的部分
识别并求解出边界条件

利用动态规划解决的一些问题：背包问题、最长公共子序列、短阵链相乘、硬币找零、图的全源最短路径

最少硬币找零问题

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
class MinCoinChange(){
  construtcor (coins) {
    this.coins = coins
    this.cache = {}
  }
  makeChange (amount) {
    let me = this
    if (!amount) { 
      return []
    }
    if (me.cache[amount]) {
      return me.cache[amount]
    }
    let min = [], newMin, newAmount
    for (let i = 0, len = me.coins.length; i < len; i++) { 
      let coin = me.coins[i]
      newAmount = amount - coin
      if (newAmount >= 0){
        newMin = me.makeChange(newAmount); 
      }
      if (
        newAmount >= 0 && 
        (newMin.length < min.length - 1 || !min.length)
        && (newMin.length || !newAmount)
        ) {
        min = [coin].concat(newMin)
        console.log('new Min ' + min + ' for ' + amount)
      } 
    }
    return (me.cache[amount] = min)
  }
}

贪心算法

贪心算法遵循一种近似解决问题的技术，期盼通过每个阶段的局部最优选择(当前最好的解)，从而达到全局的最优(全局最优解)

贪心算法解决最少硬币找零问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class MinCoinChange(coins){
  construtcor (coins) {
    this.coins = coins
  }
  makeChange (amount) {
    let change = [],
      total = 0
    for (let i = coins.length; i >= 0; i--) {
      let coin = coins[i]
      while (total + coin <= amount) {
        change.push(coin)
        total += coin
      } 
    }
    return change
  }
}

贪心算法对于最少硬币找零问题的解决，是基于硬币数组里的数值是有序的，从大到小排列。
此外，比起动态规划算法而言，贪心算法更简单、更快。然而，如我们所见，它并不总是得到最优答案。但是综合来看，它相对执行时间来说，输出了一个可以接受的解。

大O表示法

大O表示法，是描述算法的性能和复杂程度。

推导大O阶，我们可以按照如下的规则来进行推导，得到的结果就是大O表示法：

  • 用常数1来取代运行时间中所有加法常数
  • 修改后的运行次数函数中，只保留最高阶项
  • 如果最高阶项存在且不是1，则去除与这个项相乘的常数

算法时间复杂度计算

  • 找出算法中的基本语句
  • 计算基本语句的执行次数的数量级
  • 用大Ο记号表示算法的时间性能（将基本语句执行次数的数量级放入大Ο记号中）
坚持原创技术分享，您的支持将鼓励我继续创作！