數(shù)據(jù)結(jié)構(gòu)
1. 哈希宴偿，hash昭齐，所有滿足 key: value 的都是哈希尿招，很抽象，
比如數(shù)組阱驾、對象就谜，都是哈希
a = [7,3,2,,8,4,7,73,1]
比較排序如冒泡、選擇排序里覆，
至少會遍歷一次比較一次丧荐，
比較排序的時間復(fù)雜度的極限，最快最快也要 nlogn
a = {
"0": 0,
"1": 6,
"2": 2,
"6": 8,
"9": 3,
"22": 76,
"66": 23,
"length": 66 //數(shù)組的length是由 最大的數(shù)字下標+1,
//中間沒寫的實際上默認為空喧枷？
}
2. 計數(shù)排序
a = [7,1,2,6,6,3,5,9,0] //數(shù)組
var index; //下標
var hash=[] //定義hash
for(var i=0; i<a.length; i++){
index = a[i]; //取出值
if(hash[index] != undefined){
hash[index] += 1; //此值出現(xiàn)次數(shù)增加
}
else{
hash[index] = 1; //此值第一次出現(xiàn)
}
}
var arr = []; //定義數(shù)組
var count; //用于計數(shù)
// 遍歷hash篮奄，將值從小到大存到新數(shù)組中
for(var i=0; i<=hash.length; i++){
count = hash[i]; // 得到i值的數(shù)量
if(count != undefined){ // count存在
for(var j=0; j<count; j++){ //假設(shè)存在多個i值
arr.push(i); // push i值
}
}
}
復(fù)雜度：O(n+max)，比快排還快
缺點：
必須要有一個hash作為計數(shù)的工具
無法對小數(shù)和負數(shù)排序（從0開始）
3. 桶排序割去，與計數(shù)排序類似
但是 計數(shù)排序是一個桶內(nèi)放一個數(shù)字
hash:{
"1": 1,
"2": 1,
"3": 1,
"4": 1,
"7": 1,
"76": 1
}
而 桶排序是一個桶內(nèi)放一定范圍內(nèi)的數(shù)字
hash:{
"1": [0,6,2,8,3], // 10以內(nèi)的數(shù)字
"2": [], // 20以內(nèi)
"3": [],
"4": [],
"5": [],
"6": [],
"7": [],
"8": [76] // 80以內(nèi)
}
桶排序還需要做二次排序
好處是縮短了空間，只用了8個桶昼丑，而計數(shù)排序用了76個桶呻逆，浪費了空間
壞處是浪費了時間，計數(shù)排序則節(jié)約了時間
排序就是菩帝，要么浪費空間咖城，要么浪費時間，
什么時候用桶排序：比如高考分數(shù)排序呼奢，100分以下一個桶……700分以下一個桶宜雀，這樣只用七個桶，而計數(shù)排序則需要700個桶握础，每分都要一個桶
桶排序是計數(shù)排序的升級
4. 基數(shù)排序
可以適應(yīng)特別特別大的數(shù)字
具體見 https://visualgo.net/bn/sorting
計數(shù)排序：很浪費桶辐董，排的次數(shù)，入一次禀综，出一次
桶排序 ：桶的個數(shù)由你定简烘，想要幾個桶就幾個桶苔严，也是入一次出一次，但是還要再排序孤澎，因為是亂的届氢，之后如何排序看情況
基數(shù)排序：桶的個數(shù)是固定的，只有10個（0~9）覆旭，排的次數(shù)由數(shù)值的位數(shù)定退子，四位數(shù)要排4次
5. 隊列 queue（一個抽象的概念）
先進先出（沒了，這就是隊列）
在現(xiàn)實生活中的例子：排隊
可以用數(shù)組實現(xiàn)型将，比如
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的排隊系統(tǒng)寂祥，那么就用隊列，先買票的人先出票
6. 棧 stack
先進后出
也可以用數(shù)組實現(xiàn)
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
數(shù)組無法直接刪除中間的一項茶敏，連表可以
用哈希（js里面用對象表示哈希）實現(xiàn)鏈表
// 這里簡寫壤靶，只用了一個變量，其它變量嵌套在內(nèi)
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不停
而數(shù)組就快很多贮乳，比如查找第n個，只需要a[n-1]就可以了
數(shù)組查詢很快恬惯，鏈表刪除很快
鏈表有2個概念
head和node
比如上面的例子向拆，還原為
var a3={
value: 3,
next: undefined
}
var a2={
value: 2,
next: a3
}
var a = {
value: 1,
next: a2
}
a就是這個鏈表的表頭，也就是head酪耳，
只要找到表頭浓恳，就可以找到后面的所有項
其它的都是節(jié)點，表頭也是節(jié)點碗暗，node
8. 樹 tree （鏈表的升級颈将，全程只有一個箭頭就是鏈表，如果中途分叉了就是樹）
只要你有層級言疗，你就要用到樹晴圾，
比如我們寫的網(wǎng)頁頁面就用到樹
dom也是樹
概念：
-層數(shù)，比如html是第一層噪奄，head與body是第二層
-深度死姚，一共有多少層
-節(jié)點個數(shù)，每一個hash就是一個節(jié)點勤篮，如上面都毒，html是一個，head是一個碰缔，body是一個
沒有兒子的節(jié)點叫做葉子節(jié)點账劲，葉子上布會再長葉子
二叉樹
就是每次最多分兩個叉，可以分一個叉
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
} } }
滿二叉樹
就是葉子是長滿的，除去葉子節(jié)點涤垫，每個節(jié)點都有兩個兒子姑尺，就是滿二叉樹
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
} } } }
二叉樹
層數(shù)i 那一層最多有幾個節(jié)點 所有層 下標
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)個節(jié)點數(shù)，
深度為k的二叉樹至多總共有2^(k+1)-1 個節(jié)點數(shù)（定義根節(jié)點所在深度 k0 = 0）;
而總計擁有節(jié)點數(shù)符合的蝠猬，稱為“滿二叉樹”切蟋，
深度為k有n個節(jié)點的二叉樹，當(dāng)且僅當(dāng)其中的每一節(jié)點榆芦，都可以和同樣深度k的滿二叉樹柄粹，序號為1到n的節(jié)點一對一對應(yīng)時，稱為“完全二叉樹”;
類型
二叉樹是一個有根樹匆绣，并且每個節(jié)點最多有2個子節(jié)點;
一棵深度為k驻右，且有2^(k+1)-1個節(jié)點的二叉樹，稱為滿二叉樹（Full Binary Tree）崎淳；
在一顆二叉樹中堪夭，除最后一層外，若其余層都是滿的拣凹，并且最后一層或者是滿的森爽，或者是在右邊缺少連續(xù)若干節(jié)點，則此二叉樹為完全二叉樹（Complete Binary Tree））
深度為k的完全二叉樹嚣镜，至少有2k個節(jié)點爬迟，至多有2(K+1)-1個節(jié)點;
比如深度為4的完全二叉樹，最少有8個節(jié)點菊匿，最多有15個節(jié)點
完全二叉樹和滿二叉樹可以用數(shù)組來實現(xiàn)
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
如果要找第三層的第一個數(shù)字
a[2^2-1] // 3
a[2^3-1] // 7 第四層第一個數(shù)字
a[2^2-1+3]// 6 第三層第四個數(shù)字
通過下標的公式就能取到第n層的第m個數(shù)字付呕，
因為這是完全二叉樹，從左到右依次存的
其它樹可以用哈希（對象）實現(xiàn)
堆排序
http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/
最大堆
最大堆調(diào)整
