moseasirius/algorithm

Algorithm and data structure

Algorithm

Algorithm and data structure

线性（排序）

树形结构

图形结构

线性问题

O（n^2) ：选择排序 插入排序 并非一无是处

O(nlogn) : 归并排序 快速排序 三路快排

​ partition->随机化->大量重复元素

​ 求逆序数的个数 k-selection

O(nlogn) : 堆排序 堆的应用：优先队列 索引堆

树形问题

二叉查找树（Binary Search Tree) 解决查找问题

二分查找法 动态维护:插入 删除 查找 遍历 顺序相关问题

并查集（Union Find） 基于rank的优化 ->路径压缩 Kruskal

图论问题

图的表示：邻接表和邻接矩阵 有向图 无向图 有权图 无权图

图的遍历 DFS BFS

连通分量 Flood Fill 寻路 走迷宫 迷宫生成 无权图的最短路径 环的判断

最小生成树问题 Minimum Spanning Tree

最短路径问题 Shortest Path Dijkstra Bellman-Ford

更多算法问题

数据结构相关

双向队列 斐波那契堆 红黑树 区间树 KD树

具体领域相关

数学： 数论 计算几何 图论 网络流

算法设计相关

分治 归并排序 快速排序 树结构

贪心 选择排序 ；堆 ；Kruskal ；Prim ；Dijkstra

递归回溯 树的遍历 ；图的遍历

动态规划 Prim ;Dijkstra