数据结构
1. 哈希，hash，所有满足 key: value 的都是哈希，很抽象，
比如数组、对象，都是哈希
a = [7,3,2,,8,4,7,73,1]
比较排序如冒泡、选择排序，
至少会遍历一次比较一次，
比较排序的时间复杂度的极限，最快最快也要 nlogn
a = {
"0": 0,
"1": 6,
"2": 2,
"6": 8,
"9": 3,
"22": 76,
"66": 23,
"length": 66 //数组的length是由 最大的数字下标+1,
//中间没写的实际上默认为空？
}
2. 计数排序
a = [7,1,2,6,6,3,5,9,0] //数组
var index; //下标
var hash=[] //定义hash
for(var i=0; i<a.length; i++){
index = a[i]; //取出值
if(hash[index] != undefined){
hash[index] += 1; //此值出现次数增加
}
else{
hash[index] = 1; //此值第一次出现
}
}
var arr = []; //定义数组
var count; //用于计数
// 遍历hash，将值从小到大存到新数组中
for(var i=0; i<=hash.length; i++){
count = hash[i]; // 得到i值的数量
if(count != undefined){ // count存在
for(var j=0; j<count; j++){ //假设存在多个i值
arr.push(i); // push i值
}
}
}
复杂度：O(n+max)，比快排还快
缺点：
必须要有一个hash作为计数的工具
无法对小数和负数排序（从0开始）
3. 桶排序，与计数排序类似
但是 计数排序是一个桶内放一个数字
hash:{
"1": 1,
"2": 1,
"3": 1,
"4": 1,
"7": 1,
"76": 1
}
而 桶排序是一个桶内放一定范围内的数字
hash:{
"1": [0,6,2,8,3], // 10以内的数字
"2": [], // 20以内
"3": [],
"4": [],
"5": [],
"6": [],
"7": [],
"8": [76] // 80以内
}
桶排序还需要做二次排序
好处是缩短了空间，只用了8个桶，而计数排序用了76个桶，浪费了空间
坏处是浪费了时间，计数排序则节约了时间
排序就是，要么浪费空间，要么浪费时间，
什么时候用桶排序：比如高考分数排序，100分以下一个桶……700分以下一个桶，这样只用七个桶，而计数排序则需要700个桶，每分都要一个桶
桶排序是计数排序的升级
4. 基数排序
可以适应特别特别大的数字
具体见 https://visualgo.net/bn/sorting
计数排序：很浪费桶，排的次数，入一次，出一次
桶排序 ：桶的个数由你定，想要几个桶就几个桶，也是入一次出一次，但是还要再排序，因为是乱的，之后如何排序看情况
基数排序：桶的个数是固定的，只有10个（0~9），排的次数由数值的位数定，四位数要排4次
5. 队列 queue（一个抽象的概念）
先进先出（没了，这就是队列）
在现实生活中的例子：排队
可以用数组实现，比如
var q=[];
q.push("alice") //入队 q["alice"]
q.push("ben") // q["alice","ben"]
q.push("jack") // q["alice","ben","jack"]
// 出队
q.shift() //alice出来 q["ben","jack"]
q.shift() //ben出来 q["jack"]
q.shift() //jack出来 q[]
有什么用?
如果你要做一个12306的排队系统，那么就用队列，先买票的人先出票
6. 栈 stack
先进后出
也可以用数组实现
var stack = []
stack.push("第1层") // stack["第1层"]
stack.push("第2层") // stack["第1层","第2层"]
stack.push("第3层") // stack["第1层","第2层","第3层"]
stack.pop() // 第3层 stack["第1层","第2层"]
stack.pop() // 第2层 stack["第1层"]
stack.pop() // 第3层 stack[]
7. 链表 linked list
数组无法直接删除中间的一项，连表可以
用哈希（js里面用对象表示哈希）实现链表
// 这里简写，只用了一个变量，其它变量嵌套在内
var a = {
value: 1,
next: {
value: 2,
next: {
value: 3,
next: undefined
}
}
}
a.value //1
a.next.value // 2
a.next.next.value //3
// 将a.next的引用改为指向a.next.next
// 从而达到删除原本的a.next,也就是 2 的效果
a.next = a.next.next
a.next // 3
a.next.next // undefiend
链表查询很慢，比如上面的a.next.next,如果有很多就需要.next不停
而数组就快很多，比如查找第n个，只需要a[n-1]就可以了
数组查询很快，链表删除很快
链表有2个概念
head和node
比如上面的例子，还原为
var a3={
value: 3,
next: undefined
}
var a2={
value: 2,
next: a3
}
var a = {
value: 1,
next: a2
}
a就是这个链表的表头，也就是head，
只要找到表头，就可以找到后面的所有项
其它的都是节点，表头也是节点，node
8. 树 tree （链表的升级，全程只有一个箭头就是链表，如果中途分叉了就是树）
只要你有层级，你就要用到树，
比如我们写的网页页面就用到树
dom也是树
概念：
-层数，比如html是第一层，head与body是第二层
-深度，一共有多少层
-节点个数，每一个hash就是一个节点，如上面，html是一个，head是一个，body是一个
没有儿子的节点叫做叶子节点，叶子上布会再长叶子
二叉树
就是每次最多分两个叉，可以分一个叉
html{
tag:html,
children:[head,body]
}
head{ body{
tag: head, tag: body,
children: [meta1, meta2] children: [h1,h2]
} }
meta1{ meta2{ h1{
tag:meta1 tag:meta2 tag:h1
} } }
满二叉树
就是叶子是长满的，除去叶子节点，每个节点都有两个儿子，就是满二叉树
html{
tag:html,
children:[head,body]
}
head{ body{
tag: head, tag: body,
children: [meta1, meta2] children: [h1,h2]
} }
meta1{ meta2{ h1{ h2{
tag:meta1 tag:meta2 tag:h1 tag:h2
} } } }
二叉树
层数i 那一层最多有几个节点 所有层 下标
0 1 2^0 1(2^1-1) 0
1 2 2^1 3(2^2-1) 1~2
2 4 2^2 7(2^3-1) 3~6
3 8 2^3 15(2^4-1) 7~14
4 16 2^4 31(2^5-1) 15~30
5 32 2^4 63(2^6-1) 31~62
二叉树的第i层至多拥有2^(i-1)个节点数，
深度为k的二叉树至多总共有2^(k+1)-1 个节点数（定义根节点所在深度 k0 = 0）;
而总计拥有节点数符合的，称为“满二叉树”，
深度为k有n个节点的二叉树，当且仅当其中的每一节点，都可以和同样深度k的满二叉树，序号为1到n的节点一对一对应时，称为“完全二叉树”;
类型
二叉树是一个有根树，并且每个节点最多有2个子节点;
一棵深度为k，且有2^(k+1)-1个节点的二叉树，称为满二叉树（Full Binary Tree）；
在一颗二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树（Complete Binary Tree））
深度为k的完全二叉树，至少有2k个节点，至多有2(K+1)-1个节点;
比如深度为4的完全二叉树，最少有8个节点，最多有15个节点
完全二叉树和满二叉树可以用数组来实现
a = [0, 1,2, 3,4,5,6, 7,8,9,10,11,12,13,14]
// 1层 2层 3层 4层
0
1 2
3 4 5 6
7 8 9 10 11 12 13 14
如果要找第三层的第一个数字
a[2^2-1] // 3
a[2^3-1] // 7 第四层第一个数字
a[2^2-1+3]// 6 第三层第四个数字
通过下标的公式就能取到第n层的第m个数字，
因为这是完全二叉树，从左到右依次存的
其它树可以用哈希（对象）实现
堆排序
http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/
最大堆
最大堆调整
