基础数据结构与算法

基础数据结构与算法

数据结构

基础数据结构

ArrayList (Vector)
LinkedList
Stack
Queue
Set
Map
Heap (PriorityQueue)

树

二叉树
平衡二叉树
完全二叉树
满二叉树
排序二叉树 (二叉查找树)
自平衡二叉查找树 (AVL树)
红黑树

多路查找树
B树(B-树)
B+树

图

图的存储：
邻接矩阵，邻接表，三元组，十字链表
算法：
深度优先搜索（DFS，Depth First Search）
广度优先搜索（BFS，Breadth First Search）
最短路径：Dijkstra，Floyd
拓扑排序（求关键路径，有向无环图DAG才有拓扑排序）
最小生成树：Kruskal

算法

思路：
暴力枚举
贪心算法
动态规划
递归+分而治之

排序算法

| Name | 时间复杂度 | 空间复杂度 | 稳定性 | | - | - | - | - | | 冒泡排序 | O(n2) | O(1) | 稳定 | | 选择排序 | O(n2) | O(1) | 不稳定 | | 插入排序 | O(n2) | O(1) | 稳定 | | 快速排序 | O(nlogn) | O(logn) | 不稳定 | | 归并排序 | O(nlogn) | O(n) | 稳定 | | 希尔排序 | O(nlogn) | O(1) | 不稳定 | | 堆排序 | O(nlogn) | O(1) | 不稳定 | | 桶排序 | O(n + k) | O(n + k) | 稳定 | | 计数排序 | O(n + k) | O(k) | 稳定 | | 基数排序 | O(n x k) | O(n + k) | 稳定 |

查找算法

遍历查找
二分查找
利用数据结构：
堆，栈，队列
哈希表，分块查找，树

字符串匹配

BF算法
KMP算法