大O符號(hào)：Big O notation离福，是由德國(guó)數(shù)論學(xué)家保羅·巴赫曼在其1892年的著作《解析數(shù)論》首先引入的
指數(shù)函數(shù)：冪 = 2N
對(duì)數(shù)函數(shù)：指數(shù) = log2N，log10N簡(jiǎn)寫(xiě)為lgN炼蛤，logeN簡(jiǎn)寫(xiě)為lnN
對(duì)數(shù)的底：logaN中妖爷，增長(zhǎng)率主要取決于N，因此O(logaN)簡(jiǎn)寫(xiě)為O(logN)
平均時(shí)間復(fù)雜度：常數(shù) c理朋、對(duì)數(shù) logN絮识、對(duì)數(shù)平方log2N、線性N嗽上、NlogN次舌、平方N2、指數(shù) 2N
鏈
鏈表 List
ArrayList：數(shù)組實(shí)現(xiàn)兽愤，查找和更新 O(c)彼念，添加和刪除 O(N)
LinkedList：雙鏈表實(shí)現(xiàn)，查找和更新 O(N)浅萧，添加和刪除 O(c)
棧 Stack
可以把雙鏈表當(dāng)做棧來(lái)操作逐沙，即后進(jìn)先出
隊(duì)列 Queue
可以把雙鏈表當(dāng)做隊(duì)列來(lái)操作，即先進(jìn)先出
樹(shù)
樹(shù)的遍歷
先序遍歷：先處理本節(jié)點(diǎn)惯殊，再處理子節(jié)點(diǎn)
中序遍歷：先處理左子樹(shù)酱吝，在處理本節(jié)點(diǎn)，最后處理由子樹(shù)
后序遍歷：先處理子節(jié)點(diǎn)土思，再處理本節(jié)點(diǎn)
二叉樹(shù)
每個(gè)枝節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)务热，二叉樹(shù)的平均高度為O(√N(yùn))，N為節(jié)點(diǎn)數(shù)
二叉查找樹(shù)
每個(gè)枝節(jié)點(diǎn)己儒，它的左子節(jié)點(diǎn)小于它崎岂，它的右子節(jié)點(diǎn)大于它
二叉查找樹(shù)的節(jié)點(diǎn)的平均高度為O(logN)，即查找闪湾、新增的平均時(shí)間為O(logN)冲甘，最壞O(n)
二叉查找樹(shù)節(jié)點(diǎn)刪除：刪除A節(jié)點(diǎn)的左子節(jié)點(diǎn)B，則查找B節(jié)點(diǎn)的右子樹(shù)的最小節(jié)點(diǎn)C，來(lái)替換B江醇。如果C不是葉節(jié)點(diǎn)濒憋，則遞歸刪除。
懶惰刪除：不實(shí)際刪除節(jié)點(diǎn)陶夜，而是標(biāo)記為假刪除
AVL樹(shù)（取名于兩個(gè)發(fā)明者名字的首字母）
帶有平衡條件的二叉查找樹(shù)凛驮，保證每個(gè)節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的高度最多差1
實(shí)現(xiàn)：A有左子節(jié)點(diǎn)B，沒(méi)有右子節(jié)點(diǎn)条辟，要給B插入左子節(jié)點(diǎn)C黔夭，會(huì)導(dǎo)致A失衡。讓B代替A的位置羽嫡，A作為B的右子節(jié)點(diǎn)本姥。最終為B有左子節(jié)點(diǎn)C，右子節(jié)點(diǎn)A
B樹(shù)(Balanced Tree of Order M杭棵，多叉平衡搜索樹(shù))
1婚惫、葉節(jié)點(diǎn)是個(gè)數(shù)組，數(shù)據(jù)項(xiàng)只保存在葉節(jié)點(diǎn)的數(shù)組中
2魂爪、枝節(jié)點(diǎn)保存兩組數(shù)據(jù)辰妙，形如[100,200] [子節(jié)點(diǎn)1，子節(jié)點(diǎn)2甫窟，子節(jié)點(diǎn)3]
3密浑、子節(jié)點(diǎn)1的數(shù)據(jù)范圍在(,100]，子節(jié)點(diǎn)2的數(shù)據(jù)范圍在[100,200]粗井，子節(jié)點(diǎn)3的數(shù)據(jù)范圍在[200,)
紅黑樹(shù)
帶有顏色標(biāo)記的二叉查找樹(shù)尔破，get\add\remove的最壞時(shí)間復(fù)雜度O(logN)
1、每個(gè)節(jié)點(diǎn)要么是紅色浇衬，要么是黑色懒构。根節(jié)點(diǎn)是黑色
2、紅色節(jié)點(diǎn)不能連續(xù)
3耘擂、任一節(jié)點(diǎn)胆剧，向下到樹(shù)末梢的任何路徑，都含有相同個(gè)數(shù)的黑色節(jié)點(diǎn)
與二叉查找樹(shù)對(duì)比：任一子樹(shù)的最長(zhǎng)路徑不大于最短路徑的兩倍醉冤，保證了查找速度
與AVL樹(shù)對(duì)比：降低了平衡條件秩霍，任何不平衡都會(huì)在三次旋轉(zhuǎn)之內(nèi)解決，使得插入和刪除的性能更高
散列
散列三要素
散列函數(shù)：輸入key蚁阳，輸出一個(gè)散列值铃绒，例如取余函數(shù)
散列表：存放數(shù)據(jù)的空間
散列沖突解決方案：解決多條數(shù)據(jù)的散列值相同的問(wèn)題
分離鏈接法（拉鏈法）：把散列值相同的數(shù)據(jù)放到鏈表中
線性探測(cè)法：一條數(shù)據(jù)在散列表上的位置已經(jīng)被占據(jù)，則把他放到下一個(gè)存儲(chǔ)單元
雙散列：一條數(shù)據(jù)在散列表上的位置已經(jīng)被占據(jù)螺捐，則把它放到2倍散列值的位置上
JAVA里的散列實(shí)現(xiàn)
數(shù)組作為散列表颠悬，數(shù)組的一項(xiàng)作為桶矮燎，拉鏈法解決散列沖突。hashCode()相同的放入一個(gè)桶赔癌，hashCode()相同并equals()的诞外，當(dāng)做重復(fù)元素。數(shù)組有一個(gè)初始長(zhǎng)度灾票，數(shù)據(jù)量到達(dá)閾值時(shí)浅乔，擴(kuò)容resize到原來(lái)的兩倍，并重新散列rehash铝条。除非發(fā)生擴(kuò)容，否則操作時(shí)間復(fù)雜度O(1)席噩，比紅黑樹(shù)快班缰。
以HashMap為例，構(gòu)造時(shí)可以傳入兩個(gè)參數(shù)initialCapacity和loadFactor悼枢，即初始容量和擴(kuò)容閾值埠忘，默認(rèn)為16和0.75。最佳初始容量為 預(yù)期數(shù)據(jù)量 / loadFactor + 1馒索。
無(wú)重復(fù)集合 Set
TreeSet：紅黑樹(shù)實(shí)現(xiàn)莹妒，有序，元素需要實(shí)現(xiàn)Comparable接口的compareTo方法绰上，不能放入null
HashSet：散列實(shí)現(xiàn)旨怠，可以放入一個(gè)null
LinkedHashSet：散列表存放數(shù)據(jù)，鏈表記錄插入順序蜈块，順序與TreeSet不同
映射 Map
TreeMap：紅黑樹(shù)實(shí)現(xiàn)
HashMap：散列實(shí)現(xiàn)鉴腻，key、value都可以為null百揭。
Hashtable：散列實(shí)現(xiàn)爽哎，key、value都不可以為null器一。每個(gè)操作方法都聲明了Synchronize课锌，線程安全，同時(shí)性能也稍低祈秕。
ConcurrentHashMap：散列實(shí)現(xiàn)渺贤，線程安全，迭代時(shí)只鎖死部分元素请毛，比Hashtable性能稍高
堆
優(yōu)先隊(duì)列 priority queue
優(yōu)先隊(duì)列通常用二叉堆來(lái)實(shí)現(xiàn)癣亚，因此二叉堆可以指代優(yōu)先隊(duì)列，簡(jiǎn)稱堆
二叉堆 binary heap
完全二叉樹(shù)：除了最后兩層获印，所有節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)述雾，且最底層節(jié)點(diǎn)從左到右緊密排列街州。可以用樹(shù)實(shí)現(xiàn)玻孟，可一樣用數(shù)組實(shí)現(xiàn)唆缴。
二叉堆：一個(gè)完全二叉樹(shù)，它的每棵子樹(shù)的根節(jié)點(diǎn)都是這個(gè)子樹(shù)的最小元素
PriorityQueue：數(shù)組式二叉堆實(shí)現(xiàn)
排序（以下排序說(shuō)的都是升序）
雙循環(huán)法
冒泡排序 平均O(n2)黍翎，最壞O(n2)
// 任一時(shí)刻面徽，數(shù)組的后部分已排好序
for (var i = 0; i < len; i++) {
for (var j = 0; j < len - i - 1; j++) { // 遍歷前部分
if (arr[j] > arr[j+1]) { // 對(duì)比相鄰元素，讓大元素往后冒泡匣掸，加入到后部分
var temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
選擇排序 平均O(n2)趟紊，最壞O(n2)
var len = arr.length;
// 任一時(shí)刻，數(shù)組的前部分已排好序
for (var i = 0; i < len - 1; i++) {
var minIndex = i;
for (var j = i + 1; j < len; j++) { // 遍歷后部分碰酝，找到最小值
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
var temp = arr[i]; // 把找到的最小值加到前部分
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
插入排序 平均O(n2)霎匈，最壞O(n2)
// 任一時(shí)刻，數(shù)組的前部分已排好序
for (var i = 1; i < array.length; i++) {
var cur = array[i];
for(var j=i-1; array[ j ] > cur; j-- ) { // 從后往前遍歷前部分送爸，將當(dāng)前元素插入到前部分
array[ j + 1] = array[ j ]; // 比當(dāng)前元素大的都往后移動(dòng)一格
}
array[ j + 1] = cur; // 將當(dāng)前元素插入
}
分組法
希爾排序 平均O(nlogn)铛嘱，最壞O(nlog2n)
var len = arr.length, gap = 1;
while(gap < len / 5) { // 動(dòng)態(tài)定義初始間隔
gap =gap*5+1; // 此計(jì)算為實(shí)踐經(jīng)驗(yàn)，gap和length的關(guān)系為 [1,1-5] [6, 6-30] [31, 31-155]
}
while (gap > 0) {
// 位置相差gap的元素分為一組袭厂，對(duì)每組進(jìn)行插入排序
for (var i = gap; i < len; i++) { // i 每加1墨吓，就進(jìn)入到了另外一組，所以對(duì)每組的排序 是 穿插進(jìn)行的
var temp = arr[i];
for (var j = i-gap; j >= 0 && arr[ j ] > temp; j-=gap) {
arr[ j+gap ] = arr[ j ];
}
arr[ j+gap ] = temp;
}
gap = Math.floor(gap / 5); // gap最后一次是 1纹磺，就是一個(gè)插入排序帖烘，但此時(shí)元素移動(dòng)可以大大減少
}
歸并排序 平均O(nlog n)，最壞O(nlog n)
function mergeSort(arr) {
var len = arr.length;
if(len < 2) { // 拆分到只有一個(gè)元素時(shí)橄杨，就當(dāng)做是排好序的數(shù)組
return arr;
}
var middle = Math.floor(len / 2), // 把數(shù)組拆分成兩半
left = mergeSort(arr.slice(0, middle)),
right = mergeSort(arr.slice(middle)); // 兩半分別排好序
return merge(left, right); // 將排好序的兩半進(jìn)行歸并
}
function merge(left, right){
var 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;
}
快速排序 平均O(n*log n)蚓让，最壞O(n2)
function quickSort(array, start, end) {
if (start < end) { // 當(dāng) start 等于end 時(shí)，就是拆分到了一個(gè)元素
var last = array[end], // 用最后一個(gè)元素 跟 其他元素比較
i = start - 1; // 標(biāo)記比last小的元素存放的位置讥珍，目前還沒(méi)有历极，所以是 -1
for (var j = start; j <= end; j++) { // 遍歷整個(gè)數(shù)組
if (array[ j ] <= last ) { // 當(dāng)前元素小于等于last，則交換到位置 i
i++;
var temp = array[ i ];
array[ i ] = array[ j ];
array[ j ] = temp;
}
}
// 將數(shù)組拆分成兩個(gè)數(shù)組衷佃，分別排序趟卸，其中一個(gè)數(shù)組都小于等于last，另一個(gè)都大于last
quickSort(array, start, i - 1); // start 到 i - 1都小于等于last
// 中間還有個(gè)array[ i ]就是 last
quickSort(array, i + 1, end); // i + 1到end都大于last
}
return array;
}
quickSort(arr,0,arr.length-1);
分桶法
以下k表示桶數(shù)
計(jì)數(shù)排序 平均O(n+k)氏义，最壞O(n+k)
把數(shù)據(jù)的值作為下標(biāo)锄列，放到一個(gè)新數(shù)組中，最后只要順次讀取新數(shù)組
限制：桶的數(shù)量（新數(shù)組的長(zhǎng)度）不小于數(shù)據(jù)的取值范圍
桶排序 平均O(n+k)惯悠，最壞O(n2)
1邻邮、遍歷數(shù)組，將相同級(jí)別的數(shù)據(jù)放到一個(gè)桶中
2克婶、分別排序每一個(gè)桶
3筒严、讀出每一個(gè)桶的數(shù)據(jù)
例如：100以內(nèi)數(shù)字的排序丹泉，根據(jù)數(shù)字的十位數(shù)，分別放到編號(hào)0-9的數(shù)組中鸭蛙，分別對(duì)每個(gè)數(shù)組排序摹恨，依次讀出每個(gè)桶里的數(shù)字
基數(shù)排序 平均O(nk)，最壞O(nk)
1娶视、遍歷數(shù)組晒哄，將相同尾數(shù)的數(shù)據(jù)放到一個(gè)桶中
2、按順序讀出所有數(shù)據(jù)肪获，再根據(jù)次尾數(shù)分別放到桶中寝凌，以此類推
3、按順序讀出所有數(shù)據(jù)
例如：對(duì)[12,11,2,1]排序孝赫，放入兩個(gè)桶[11,1][12,2]较木，讀出[11,1,12,2]，再次入桶[1,2][11,12]寒锚，再次讀出[1,2,11,12]
二叉樹(shù)法
堆排序 平均O(nlog n)，最壞O(nlog n)
即每次從二叉堆中取出堆頂元素
常見(jiàn)問(wèn)題與方案
topK
問(wèn)題：從N個(gè)數(shù)中违孝，找到最大的K個(gè)數(shù)
方案：讀取前K個(gè)數(shù)刹前，創(chuàng)建一個(gè)堆頂為最小數(shù)的堆；讀取后N-K個(gè)數(shù)雌桑，比堆頂大則刪除堆頂喇喉，并插入堆；時(shí)間復(fù)雜度為O(N*logK)
尋找中位數(shù)
等同于找出 top N/2
一個(gè)整數(shù)的二進(jìn)制表示中1的個(gè)數(shù)
while(n>0){
if((n&1)==1){result++}
n = n>>1 // 每次消除一位
}
或
while(n>0){
result ++;
n = n&(n-1) // 每次消除一個(gè)1
}
