时间复杂度
通常使用最差的时间复杂度来衡量一个算法的好坏。
常数时间 O(1) 代表这个操作和数据量没关系，是一个固定时间的操作，比如说四则运算。
对于一个算法来说，可能会计算出如下操作次数 a * n + 1，n 代表数据量。那么该算法的时间复杂度就是 O(n)。因为我们在计算时间复杂度的时候，数据量通常是非常大的，这时候低阶项和常数项可以忽略不计。
当然可能会出现两个算法都是 O(n) 的时间复杂度，那么对比两个算法的好坏就要通过对比低阶项和常数项了。
位运算
位运算在算法中很有用，速度可以比四则运算快很多。
在学习位运算之前应该知道十进制如何转二进制，二进制如何转十进制。这里说明下简单的计算方式：
- 十进制
33可以看成是32 + 1，并且33应该是六位二进制的（因为33近似32，而32是2的五次方，所以是六位），那么 十进制33就是100001，只要是2的次方，那么就是1否则都为0 - 那么二进制
100001同理，首位是2^5，末位是2^0，相加得出33
按位非 ~
按位取反：
~8 // -> -9
// ~ 1000 -> 0111 -> -9
2
按位与 &
对应位都为 1，结果才为 1：
8 & 7 // -> 0
// 1000 & 0111 -> 0000 -> 0
2
按位或 |
其中一位为 1，结果才为 1：
8 | 7 // -> 15
// 1000 | 0111 -> 1111 -> 15
2
按位异或 ^
对应位不同，结果才为 1：
8 ^ 7 // -> 15
8 ^ 8 // -> 0
// 1000 ^ 0111 -> 1111 -> 15
// 1000 ^ 1000 -> 0000 -> 0
2
3
4
从以上代码中可以发现按位异或就是不进位加法。
算数左移 <<
10 << 1 // -> 20
左移就是将二进制全部往左移动，10 在二进制中表示为 1010 ，左移一位后变成 10100 ，转换为十进制也就是 20，所以基本可以把左移看成以下公式 a * (2 ^ b)。
算数右移 >>
10 >> 1 // -> 5
算数右移就是将二进制全部往右移动并去除多余的右边，10 在二进制中表示为 1010 ，右移一位后变成 101 ，转换为十进制也就是 5，所以基本可以把右移看成以下公式 a / (2 ^ b)。
右移很好用，比如可以用在二分算法中取中间值。
13 >> 1 // -> 6
逻辑右移 >>>
逻辑右移表示连同符号也一起右移，无符号右移会把负数的二进制码当成正数的二进制码：
-1 >>> 0 // -> 4294967295
虽然-1 没有发生向右位移, 但是-1 的二进制码, 已经变成了正数的二进制码。
面试题：两个数不使用四则运算得出和
这道题中可以按位异或，因为按位异或就是不进位加法，8 ^ 8 = 0 如果进位了，就是 16 了，所以我们只需要将两个数进行异或操作，然后进位。那么也就是说两个二进制都是 1 的位置，左边应该有一个进位 1，所以可以得出以下公式 a + b = (a ^ b) + ((a & b) << 1) ，然后通过迭代的方式模拟加法：
function sum(a, b) {
if (a == 0) return b
if (b == 0) return a
let newA = a ^ b
let newB = (a & b) << 1
return sum(newA, newB)
}
2
3
4
5
6
7
排序
以下两个函数是排序中会用到的通用函数，就不一一写了：
function checkArray(array) {
if (!array || array.length <= 2) return
}
function swap(array, left, right) {
let rightValue = array[right]
array[right] = array[left]
array[left] = rightValue
}
2
3
4
5
6
7
8
冒泡排序
冒泡排序的原理如下，从第一个元素开始，把当前元素和下一个索引元素进行比较。如果当前元素大，那么就交换位置，重复操作直到比较到最后一个元素，那么此时最后一个元素就是该数组中最大的数。下一轮重复以上操作，但是此时最后一个元素已经是最大数了，所以不需要再比较最后一个元素，只需要比较到 length - 1 的位置。
以下是实现该算法的代码：
function bubble(array) {
checkArray(array)
for (let i = array.length - 1; i > 0; i--) {
// 从 0 到 `length - 1` 遍历
for (let j = 0; j < i; j++) {
if (array[j] > array[j + 1]) swap(array, j, j + 1)
}
}
return array
}
2
3
4
5
6
7
8
9
10
该算法的操作次数是一个等差数列 N + (N - 1) + (N- 2) + 1 ，去掉常数项以后得出时间复杂度是 O(N^2)。
插入排序
插入排序的原理如下。第一个元素默认是已排序元素，取出下一个元素和当前元素比较，如果当前元素大就交换位置。那么此时第一个元素就是当前的最小数，所以下次取出操作从第三个元素开始，向前对比，重复之前的操作。
以下是实现该算法的代码：
function insertion(array) {
checkArray(array)
for (let i = 1; i < array.length; i++) {
for (let j = i - 1; j >= 0 && array[j] > array[j + 1]; j--) swap(array, j, j + 1)
}
return array
}
2
3
4
5
6
7
该算法的操作次数是一个等差数列 N + (N - 1) + (N - 2) + 1 ，去掉常数项以后得出时间复杂度是 O(N^2)。
选择排序
选择排序的原理如下。遍历数组，设置最小值的索引为 0，如果取出的值比当前最小值小，就替换最小值索引，遍历完成后，将第一个元素和最小值索引上的值交换。如上操作后，第一个元素就是数组中的最小值，下次遍历就可以从索引 1 开始重复上述操作。
以下是实现该算法的代码：
function selection(array) {
checkArray(array)
for (let i = 0; i < array.length - 1; i++) {
let minIndex = i
for (let j = i + 1; j < array.length; j++) {
minIndex = array[j] < array[minIndex] ? j : minIndex
}
swap(array, i, minIndex)
}
return array
}
2
3
4
5
6
7
8
9
10
11
该算法的操作次数是一个等差数列 N + (N - 1) + (N - 2) + 1 ，去掉常数项以后得出时间复杂度是 O(N^2)。
快速排序
快速排序的原理如下。随机选取一个数组中的值作为基准值，从左至右取值与基准值对比大小。比基准值小的放数组左边，大的放右边，对比完成后将基准值和第一个比基准值大的值交换位置。然后将数组以基准值的位置分为两部分，继续递归以上操作。
以下是实现该算法的代码：
function sort(array) {
checkArray(array);
quickSort(array, 0, array.length - 1);
return array;
}
function quickSort(array, left, right) {
if (left < right) {
swap(array, , right)
// 随机取值，然后和末尾交换，这样做比固定取一个位置的复杂度略低
let indexs = part(array, parseInt(Math.random() * (right - left + 1)) + left, right);
quickSort(array, left, indexs[0]);
quickSort(array, indexs[1] + 1, right);
}
}
function part(array, left, right) {
let less = left - 1;
let more = right;
while (left < more) {
if (array[left] < array[right]) {
// 当前值比基准值小，`less` 和 `left` 都加一
++less;
++left;
} else if (array[left] > array[right]) {
// 当前值比基准值大，将当前值和右边的值交换
// 并且不改变 `left`，因为当前换过来的值还没有判断过大小
swap(array, --more, left);
} else {
// 和基准值相同，只移动下标
left++;
}
}
// 将基准值和比基准值大的第一个值交换位置
// 这样数组就变成 `[比基准值小, 基准值, 比基准值大]`
swap(array, right, more);
return [less, more];
}
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
该算法的复杂度和归并排序是相同的，但是额外空间复杂度比归并排序少，只需 O(logN)。
归并排序
归并排序的原理如下。递归的将数组两两分开直到最多包含两个元素，然后将数组排序合并，最终合并为排序好的数组。假设我有一组数组 [3, 1, 2, 8, 9, 7, 6]，中间数索引是 3，先排序数组 [3, 1, 2, 8] 。在这个左边数组上，继续拆分直到变成数组包含两个元素（如果数组长度是奇数的话，会有一个拆分数组只包含一个元素）。然后排序数组 [3, 1] 和 [2, 8] ，然后再排序数组 [1, 3, 2, 8] ，这样左边数组就排序完成，然后按照以上思路排序右边数组，最后将数组 [1, 2, 3, 8] 和 [6, 7, 9] 排序。
以下是实现该算法的代码：
function sort(array) {
checkArray(array)
mergeSort(array, 0, array.length - 1)
return array
}
function mergeSort(array, left, right) {
// 左右索引相同说明已经只有一个数
if (left === right) return
// 等同于 `left + (right - left) / 2`
// 相比 `(left + right) / 2` 来说更加安全，不会溢出
// 使用位运算是因为位运算比四则运算快
let mid = parseInt(left + ((right - left) >> 1))
mergeSort(array, left, mid)
mergeSort(array, mid + 1, right)
let help = []
let i = 0
let p1 = left
let p2 = mid + 1
while (p1 <= mid && p2 <= right) {
help[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++]
}
while (p1 <= mid) {
help[i++] = array[p1++]
}
while (p2 <= right) {
help[i++] = array[p2++]
}
for (let i = 0; i < help.length; i++) {
array[left + i] = help[i]
}
return array
}
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
以上算法使用了递归的思想。递归的本质就是压栈，每递归执行一次函数，就将该函数的信息（比如参数，内部的变量，执行到的行数）压栈，直到遇到终止条件，然后出栈并继续执行函数。对于以上递归函数的调用轨迹如下：
mergeSort(data, 0, 6) // mid = 3
mergeSort(data, 0, 3) // mid = 1
mergeSort(data, 0, 1) // mid = 0
mergeSort(data, 0, 0) // 遇到终止，回退到上一步
mergeSort(data, 1, 1) // 遇到终止，回退到上一步
// 排序 p1 = 0, p2 = mid + 1 = 1
// 回退到 `mergeSort(data, 0, 3)` 执行下一个递归
mergeSort(2, 3) // mid = 2
mergeSort(3, 3) // 遇到终止，回退到上一步
// 排序 p1 = 2, p2 = mid + 1 = 3
// 回退到 `mergeSort(data, 0, 3)` 执行合并逻辑
// 排序 p1 = 0, p2 = mid + 1 = 2
// 执行完毕回退
// 左边数组排序完毕，右边也是如上轨迹
2
3
4
5
6
7
8
9
10
11
12
13
14
该算法的操作次数是可以这样计算：递归了两次，每次数据量是数组的一半，并且最后把整个数组迭代了一次，所以得出表达式 2T(N / 2) + T(N) （T 代表时间，N 代表数据量）。根据该表达式可以套用 该公式 得出时间复杂度为 O(NlogN)。
堆排序
堆排序利用了二叉堆的特性来做，二叉堆通常用数组表示，并且二叉堆是一颗完全二叉树（所有叶节点（最底层的节点）都是从左往右顺序排序，并且其他层的节点都是满的）。二叉堆又分为大根堆与小根堆。
- 大根堆是某个节点的所有子节点的值都比他小
- 小根堆是某个节点的所有子节点的值都比他大
堆排序的原理就是组成一个大根堆或者小根堆。以小根堆为例，某个节点的左边子节点索引是 i * 2 + 1，右边是 i * 2 + 2，父节点是 (i - 1) /2。
- 首先遍历数组，判断该节点的父节点是否比他小，如果小就交换位置并继续判断，直到他的父节点比他大
- 重新以上操作 1，直到数组首位是最大值
- 然后将首位和末尾交换位置并将数组长度减一，表示数组末尾已是最大值，不需要再比较大小
- 对比左右节点哪个大，然后记住大的节点的索引并且和父节点对比大小，如果子节点大就交换位置
- 重复以上操作 3 - 4 直到整个数组都是大根堆。
以下是实现该算法的代码：
function heap(array) {
checkArray(array)
// 将最大值交换到首位
for (let i = 0; i < array.length; i++) {
heapInsert(array, i)
}
let size = array.length
// 交换首位和末尾
swap(array, 0, --size)
while (size > 0) {
heapify(array, 0, size)
swap(array, 0, --size)
}
return array
}
function heapInsert(array, index) {
// 如果当前节点比父节点大，就交换
while (array[index] > array[parseInt((index - 1) / 2)]) {
swap(array, index, parseInt((index - 1) / 2))
// 将索引变成父节点
index = parseInt((index - 1) / 2)
}
}
function heapify(array, index, size) {
let left = index * 2 + 1
while (left < size) {
// 判断左右节点大小
let largest = left + 1 < size && array[left] < array[left + 1] ? left + 1 : left
// 判断子节点和父节点大小
largest = array[index] < array[largest] ? largest : index
if (largest === index) break
swap(array, index, largest)
index = largest
left = index * 2 + 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
以上代码实现了小根堆，如果需要实现大根堆，只需要把节点对比反一下就好，该算法的复杂度是 O(NlogN)。
系统排序
每个语言的排序内部实现都是不同的。
对于 JS 来说，数组长度大于 10 会采用快排，否则使用插入排序 源码实现 。选择插入排序是因为虽然时间复杂度很差，但是在数据量很小的情况下和 O(N * logN) 相差无几，然而插入排序需要的常数时间很小，所以相对别的排序来说更快。
对于 Java 来说，还会考虑内部的元素的类型。对于存储对象的数组来说，会采用稳定性好的算法。稳定性的意思就是对于相同值来说，相对顺序不能改变。
树
二叉遍历
先序遍历表示先访问根节点，然后访问左节点，最后访问右节点。
中序遍历表示先访问左节点，然后访问根节点，最后访问右节点。
后序遍历表示先访问左节点，然后访问右节点，最后访问根节点。
递归实现
递归实现相当简单，代码如下：
function TreeNode(val) {
this.val = val
this.left = this.right = null
}
var traversal = function(root) {
if (root) {
// 先序
console.log(root)
traversal(root.left)
// 中序
// console.log(root);
traversal(root.right)
// 后序
// console.log(root);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
对于递归的实现来说，只需要理解每个节点都会被访问三次就明白为什么这样实现了。
非递归实现
非递归实现使用了栈的结构，通过栈的先进后出模拟递归实现。
以下是先序遍历代码实现：
function pre(root) {
if (root) {
let stack = []
// 先将根节点 push
stack.push(root)
// 判断栈中是否为空
while (stack.length > 0) {
// 弹出栈顶元素
root = stack.pop()
console.log(root)
// 因为先序遍历是先左后右，栈是先进后出结构
// 所以先 push 右边再 push 左边
if (root.right) {
stack.push(root.right)
}
if (root.left) {
stack.push(root.left)
}
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
以下是中序遍历代码实现：
function mid(root) {
if (root) {
let stack = []
// 中序遍历是先左再根最后右
// 所以首先应该先把最左边节点遍历到底依次 push 进栈
// 当左边没有节点时，就打印栈顶元素，然后寻找右节点
// 对于最左边的叶节点来说，可以把它看成是两个 null 节点的父节点
// 左边打印不出东西就把父节点拿出来打印，然后再看右节点
while (stack.length > 0 || root) {
if (root) {
stack.push(root)
root = root.left
} else {
root = stack.pop()
console.log(root)
root = root.right
}
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
以下是后序遍历代码实现，该代码使用了两个栈来实现遍历，相比一个栈的遍历来说要容易理解很多：
function pos(root) {
if (root) {
let stack1 = []
let stack2 = []
// 后序遍历是先左再右最后根
// 所以对于一个栈来说，应该先 push 根节点
// 然后 push 右节点，最后 push 左节点
stack1.push(root)
while (stack1.length > 0) {
root = stack1.pop()
stack2.push(root)
if (root.left) {
stack1.push(root.left)
}
if (root.right) {
stack1.push(root.right)
}
}
while (stack2.length > 0) {
console.log(s2.pop())
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
中序遍历节点
实现这个算法的前提是节点有一个 parent 的指针指向父节点，根节点指向 null：
前驱节点
对于节点 2 来说，他的前驱节点就是 4 ，按照中序遍历原则，可以得出以下结论
- 如果选取的节点的左节点不为空，就找该左节点最右的节点。对于节点
1来说，他有左节点2，那么节点2的最右节点就是5 - 如果左节点为空，且目标节点是父节点的右节点，那么前驱节点为父节点。对于节点
5来说，没有左节点，且是节点2的右节点，所以节点2是前驱节点 - 如果左节点为空，且目标节点是父节点的左节点，向上寻找到第一个是父节点的右节点的节点。对于节点
6来说，没有左节点，且是节点3的左节点，所以向上寻找到节点1，发现节点3是节点 1 的右节点，所以节点1是节点6的前驱节点
以下是算法实现：
function predecessor(node) {
if (!node) return
// 结论 1
if (node.left) {
return getRight(node.left)
} else {
let parent = node.parent
// 结论 2 3 的判断
while (parent && parent.right === node) {
node = parent
parent = node.parent
}
return parent
}
}
function getRight(node) {
if (!node) return
node = node.right
while (node) node = node.right
return node
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
后继节点
对于节点 2 来说，他的后继节点就是 5 ，按照中序遍历原则，可以得出以下结论：
- 如果有右节点，就找到该右节点的最左节点。对于节点
1来说，他有右节点3，那么节点3的最左节点就是6 - 如果没有右节点，就向上遍历直到找到一个节点是父节点的左节点。对于节点
5来说，没有右节点，就向上寻找到节点2，该节点是父节点1的左节点，所以节点1是后继节点
以下是算法实现：
function successor(node) {
if (!node) return
// 结论 1
if (node.right) {
return getLeft(node.right)
} else {
// 结论 2
let parent = node.parent
// 判断 parent 为空
while (parent && parent.left === node) {
node = parent
parent = node.parent
}
return parent
}
}
function getLeft(node) {
if (!node) return
node = node.left
while (node) node = node.left
return node
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
树的深度
树的最大深度：该题目来自 Leetcode，题目需要求出一颗二叉树的最大深度
以下是算法实现：
var maxDepth = function(root) {
if (!root) return 0
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
}
2
3
4
对于该递归函数可以这样理解：一旦没有找到节点就会返回 0，每弹出一次递归函数就会加 1，树有三层就会得到 3。