dzhai/basic-algorithm-java-version

Some basic algorithms and data structures based on "Algorithms Fourth Edition"

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 最小堆