大O符号：Big O notation，是由德国数论学家保罗·巴赫曼在其1892年的著作《解析数论》首先引入的
指数函数：幂 = 2^N
对数函数：指数 = log₂N，log₁₀N简写为lgN，log_eN简写为lnN
对数的底：log_aN中，增长率主要取决于N，因此O(log_aN)简写为O(logN)
平均时间复杂度：常数 c、对数 logN、对数平方log²N、线性N、NlogN、平方N²、指数 2^N

链

链表 List
ArrayList：数组实现，查找和更新 O(c)，添加和删除 O(N)
LinkedList：双链表实现，查找和更新 O(N)，添加和删除 O(c)

栈 Stack
可以把双链表当做栈来操作，即后进先出

队列 Queue
可以把双链表当做队列来操作，即先进先出

树

树的遍历
先序遍历：先处理本节点，再处理子节点
中序遍历：先处理左子树，在处理本节点，最后处理由子树
后序遍历：先处理子节点，再处理本节点

二叉树
每个枝节点最多有两个子节点，二叉树的平均高度为O(√N)，N为节点数

二叉查找树
每个枝节点，它的左子节点小于它，它的右子节点大于它
二叉查找树的节点的平均高度为O(logN)，即查找、新增的平均时间为O(logN)，最坏O(n)
二叉查找树节点删除：删除A节点的左子节点B，则查找B节点的右子树的最小节点C，来替换B。如果C不是叶节点，则递归删除。
懒惰删除：不实际删除节点，而是标记为假删除

AVL树（取名于两个发明者名字的首字母）
带有平衡条件的二叉查找树，保证每个节点的左子树和右子树的高度最多差1
实现：A有左子节点B，没有右子节点，要给B插入左子节点C，会导致A失衡。让B代替A的位置，A作为B的右子节点。最终为B有左子节点C，右子节点A

B树(Balanced Tree of Order M，多叉平衡搜索树)
1、叶节点是个数组，数据项只保存在叶节点的数组中
2、枝节点保存两组数据，形如[100,200] [子节点1，子节点2，子节点3]
3、子节点1的数据范围在(,100]，子节点2的数据范围在[100,200]，子节点3的数据范围在[200,)

红黑树
带有颜色标记的二叉查找树，get\add\remove的最坏时间复杂度O(logN)
1、每个节点要么是红色，要么是黑色。根节点是黑色
2、红色节点不能连续
3、任一节点，向下到树末梢的任何路径，都含有相同个数的黑色节点
与二叉查找树对比：任一子树的最长路径不大于最短路径的两倍，保证了查找速度
与AVL树对比：降低了平衡条件，任何不平衡都会在三次旋转之内解决，使得插入和删除的性能更高

散列

散列三要素
散列函数：输入key，输出一个散列值，例如取余函数
散列表：存放数据的空间
散列冲突解决方案：解决多条数据的散列值相同的问题

分离链接法（拉链法）：把散列值相同的数据放到链表中
线性探测法：一条数据在散列表上的位置已经被占据，则把他放到下一个存储单元
双散列：一条数据在散列表上的位置已经被占据，则把它放到2倍散列值的位置上

JAVA里的散列实现
数组作为散列表，数组的一项作为桶，拉链法解决散列冲突。hashCode()相同的放入一个桶，hashCode()相同并equals()的，当做重复元素。数组有一个初始长度，数据量到达阈值时，扩容resize到原来的两倍，并重新散列rehash。除非发生扩容，否则操作时间复杂度O(1)，比红黑树快。
以HashMap为例，构造时可以传入两个参数initialCapacity和loadFactor，即初始容量和扩容阈值，默认为16和0.75。最佳初始容量为 预期数据量 / loadFactor + 1。

无重复集合 Set
TreeSet：红黑树实现，有序，元素需要实现Comparable接口的compareTo方法，不能放入null
HashSet：散列实现，可以放入一个null
LinkedHashSet：散列表存放数据，链表记录插入顺序，顺序与TreeSet不同

映射 Map
TreeMap：红黑树实现
HashMap：散列实现，key、value都可以为null。
Hashtable：散列实现，key、value都不可以为null。每个操作方法都声明了Synchronize，线程安全，同时性能也稍低。
ConcurrentHashMap：散列实现，线程安全，迭代时只锁死部分元素，比Hashtable性能稍高

堆

优先队列 priority queue
优先队列通常用二叉堆来实现，因此二叉堆可以指代优先队列，简称堆

二叉堆 binary heap
完全二叉树：除了最后两层，所有节点都有两个子节点，且最底层节点从左到右紧密排列。可以用树实现，可一样用数组实现。
二叉堆：一个完全二叉树，它的每棵子树的根节点都是这个子树的最小元素
PriorityQueue：数组式二叉堆实现

排序（以下排序说的都是升序）

双循环法

冒泡排序 平均O(n²)，最坏O(n²)

// 任一时刻，数组的后部分已排好序
for (var i = 0; i < len; i++) {
　for (var j = 0; j < len - i - 1; j++) {   // 遍历前部分
　　if (arr[j] > arr[j+1]) {                   // 对比相邻元素，让大元素往后冒泡，加入到后部分
　　　var temp = arr[j+1];  
　　　arr[j+1] = arr[j];
　　　arr[j] = temp;
　　}
　}
}

选择排序 平均O(n²)，最坏O(n²)

var len = arr.length;
// 任一时刻，数组的前部分已排好序
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(n²)，最坏O(n²)

// 任一时刻，数组的前部分已排好序
for (var i = 1; i < array.length; i++) {
　var cur = array[i];
　for(var j=i-1; array[ j ] > cur; j-- ) {    // 从后往前遍历前部分，将当前元素插入到前部分
　　　array[ j + 1] = array[ j ];            // 比当前元素大的都往后移动一格
　}
　array[ j + 1] = cur;      // 将当前元素插入
}

分组法

希尔排序 平均O(nlogn)，最坏O(nlog²n)

var len = arr.length, gap = 1;
while(gap < len / 5) {  // 动态定义初始间隔
　　gap =gap*5+1;    // 此计算为实践经验，gap和length的关系为 [1,1-5] [6, 6-30] [31, 31-155]
}
while (gap > 0) {
   // 位置相差gap的元素分为一组，对每组进行插入排序
　for (var i = gap; i < len; i++) {  // i 每加1，就进入到了另外一组，所以对每组的排序 是 穿插进行的
　　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，就是一个插入排序，但此时元素移动可以大大减少
}

归并排序 平均O(nlog n)，最坏O(nlog n)

function mergeSort(arr) {
　　var len = arr.length;
　　if(len < 2) {      // 拆分到只有一个元素时，就当做是排好序的数组
　　　　return arr;
　　}
　　var middle = Math.floor(len / 2),   // 把数组拆分成两半
　　left = mergeSort(arr.slice(0, middle)), 
　　right = mergeSort(arr.slice(middle));  // 两半分别排好序
　　return merge(left, right);   // 将排好序的两半进行归并
}
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(n²)

function quickSort(array, start, end) {
　　if (start < end) {       // 当 start 等于end 时，就是拆分到了一个元素
　　　　var last = array[end],          // 用最后一个元素 跟 其他元素比较
                    i = start - 1;                   // 标记比last小的元素存放的位置，目前还没有，所以是 -1
　　　　for (var j = start; j <= end; j++) {   // 遍历整个数组
　　　　　　if (array[ j ] <= last ) {   // 当前元素小于等于last，则交换到位置 i
　　　　　　　　i++;
　　　　　　　　var temp = array[ i ];
　　　　　　　　array[ i ] = array[ j ];
　　　　　　　　array[ j ] = temp;
　　　　　　}
　　　　}
              // 将数组拆分成两个数组，分别排序，其中一个数组都小于等于last，另一个都大于last 
　　　　quickSort(array, start, i - 1);  // start 到 i - 1都小于等于last
              // 中间还有个array[ i ]就是 last
　　　　quickSort(array, i + 1, end);  // i + 1到end都大于last
　　}
　　return array;
}
quickSort(arr,0,arr.length-1);

分桶法

以下k表示桶数

计数排序 平均O(n+k)，最坏O(n+k)
把数据的值作为下标，放到一个新数组中，最后只要顺次读取新数组
限制：桶的数量（新数组的长度）不小于数据的取值范围

桶排序 平均O(n+k)，最坏O(n²)
1、遍历数组，将相同级别的数据放到一个桶中
2、分别排序每一个桶
3、读出每一个桶的数据
例如：100以内数字的排序，根据数字的十位数，分别放到编号0-9的数组中，分别对每个数组排序，依次读出每个桶里的数字

基数排序 平均O(nk)，最坏O(nk)
1、遍历数组，将相同尾数的数据放到一个桶中
2、按顺序读出所有数据，再根据次尾数分别放到桶中，以此类推
3、按顺序读出所有数据
例如：对[12,11,2,1]排序，放入两个桶[11,1][12,2]，读出[11,1,12,2]，再次入桶[1,2][11,12]，再次读出[1,2,11,12]

二叉树法

堆排序 平均O(nlog n)，最坏O(nlog n)
即每次从二叉堆中取出堆顶元素

常见问题与方案

topK

问题：从N个数中，找到最大的K个数
方案：读取前K个数，创建一个堆顶为最小数的堆；读取后N-K个数，比堆顶大则删除堆顶，并插入堆；时间复杂度为O(N*logK)

寻找中位数

等同于找出 top N/2

一个整数的二进制表示中1的个数

while(n>0){
if((n&1)==1){result++}
n = n>>1 // 每次消除一位
}
或
while(n>0){
result ++;
n = n&(n-1) // 每次消除一个1
}