Basic Algorithms Implementation

---

本项目包含一些基本算法的Java版本实现。

注：部分代码直接整理自Algorithms Fourth Edition

---

算法实现

排序

• HeapSort 堆排序
• InsertSort 插入排序
• InsertSortBinary 二分优化插入排序
• InsertSortImproved 各种优化后的插入排序
• MergeSortButtonUp 自底向上堆排序
• MergeSortTopDown 自顶向下堆排序
• MergeSortTopDownImprove 自顶向下堆排序优化版
• QuickSort 普通快速排序
• QuickSort3Way 三向切分快速排序
• QuickSortFast3Way 优化三向切分快速排序
• QuickSortImprove 普通快速排序优化版
• QuickSortNonRecursive 非递归实现快速排序
• SelectionSort 选择排序
• ShellSort 希尔排序

搜索

• BST 二叉查找树

字符串相关

• LSD 低位优先的字符串排序
• MSD 高位优先的字符串排序
• TrieST Trie树实现符号表
• TST 三向单词查找树
• NaiveSearch 子串查找暴力解法
• KMPSearch KMP算法求子串

图相关

• DepthFirstSearch 深度优先搜索
• DepthFirstPaths 深度优先搜索路径
• BreadthFirstPaths 广度优先搜索路径
• Cycle 判断无向图是否有环
• CC 找出无向图所有连通分量
• TwoColor 判断是否为二分图
• DepthFirstDirectedPaths 深度优先搜索有向图路径
• BreadthFirstDirectedPaths 广度优先搜索有向图路径
• DepthFirstOrder 深度优先产生前序、后序和逆后序节点遍历
• DirectedCycle 有向图判断是否有环
• DirectedDFS 有向图深度优先遍历
• KosarajuSCC 有向图求强连通分量
• Topological 求拓扑排序
• TopologicalQueue 拓扑排序队列实现
• TransitiveClosure 求传递闭包
• DijkstraSP Dijkstra算法求最短路径
• BellmanFordSP Bellman-Ford算法求最短路径
• PrimMST Prim算法求最小生成树
• LazyPrimMST Prim算法延时版实现

其他数据结构

• IndexMinPQ 最小索引堆
• MaxPQ 最大堆
• MinPQ 最小堆