分类目录归档：算法基础
比较类排序: 通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序: 不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时 间下界，以线性时间运行，因此也称为线性时间非比较类排序。
排序算法
比较类排序
交换排序
冒泡排序
快速排序
插入排序
简单插入排序
希尔排序
选择排序
哈希表(hash table)， 也叫散列表，是根据关键码值(key value) 而直接进行访问的数据结构 它通过贝把关键码值映射到表中的一个位置来访问记录，以加快查找的速度。 这个映射函数叫做散列函数(hash function)，存放记录的数组叫做哈希表(或散列表)
key - value对，key不重复
new HashMap()/ new TreeMap()
map.set(key, value)
map.get(key)
map.has(key)
map.size()
map.clear()
不重复元素集合
new Ha栈只支持两个基本操作：入栈push()和出栈pop()
用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈
不管是顺序栈还是链式栈，我们存储数据只需要一个大小为n的数组就够了。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是O(1)
不管是顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度都是O(1)。
注意，这里存储数据需要一个大小为n的数组，并不是说空间复杂度就是O(n)。因为，这n个空间是必须的，无法省掉。所以我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。
最好情况时间复杂度是O
队列跟栈一样，也是一种操作受限的线性表数据结构
用数组实现的队列叫作 顺序队列，用链表实现的队列叫作 链式队列
最基本的操作有两个：入队enqueue()，放一个数据到队列尾部；出队dequeue()，从队列头部取一个元素
高性能队列Disruptor、Linux环形缓存，都用到了循环并发队列；Java concurrent并发包利用ArrayBlockingQueue来实现公平锁
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据 数组是线性表（Linear List）。顾名思义，线性表就是数据排成像一条线一样的结构。 每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构 而与它相对立的概念是非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。
| 操作 | 复杂度 | 备注 |
|---|---|---|
| Access | O(1) | |
| 插入 insert | O(n) | 头O(n), 尾O(1), 平均O(n/2) 即 O(n) |
| 删除 delete | O(n) | 头O(n), |
复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系
和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点
复杂度量级，我们可以粗略地分为两类，多项式量级 和 非多项式量级。其中，非多项式量级只有两个：O(2n)和O(n!)
我们把时间复杂度为非多项式量级的算法问题叫作NP（Non-Deterministic Polynomial，非确定多项式）问题
当数据规模n越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法
算
需要掌握常见的10个数据结构与10个算法：
10个数据结构：
数组(Array)、链表(LinkedList)、栈(Stack)、队列(Queue, 优先队列 PriorityQueue)、散列表(HashTable)、二叉树(tree/Binary Search Tree)、堆、跳表、图(graph)、Trie树；
10个算法：
递归(Recursion)、排序、二分查找、搜索(BST(breadth-first)，DST(Depth-first))、哈希算法、贪心算法(Greedy)、分治算法(Divide and Conquer)、回溯算法(backtrace)、动态规划(D
