Play Data Structure & Algorithm with Golang

使用 Golang 实现常用的数据结构和算法。

排序算法

• 选择排序
• 插入排序
• 冒泡排序
• 归并排序
• 希尔排序

归并排序

• 自顶向下
• 自底向上

快速排序

• 一路快排
• 二路快排
• 三路速排

排序算法对比

算法名称	时间复杂度	空间复杂度	特殊用例
选择排序	${O(n^2)}$	${O(1)}$	数组完全有序时，时间复杂度${O(n)}$
插入排序	${O(n^2)}$	${O(1)}$
冒泡排序	${O(n^2)}$	${O(1)}$
归并排序	$O(nlogN)$	${O(n)}$	数组完全有序时，时间复杂度${O(n)}$
快速排序	$O(nlogN)*$	${O(1)}$	数组元素完全相同时，三路快排时间复杂度为${O(n)}$
堆排序	$O(nlogN)$	${O(1)}$
希尔排序	$O(nlogN)-O(n^{2})$	${O(1)}$

非比较排序

• LSD
• MSD
• 桶排序

动态数组 - Dynamic Array

• 动态数组

链表 - Linked List

栈 - Stack

• 动态数组实现栈

队列 - Queue

• 动态数组实现队列
• 循环数组实现队列

堆 - Heap

• 最大堆
• 最小堆

二叉搜索树 - Binary Search Tree

• 二叉搜索树
• 自平衡二叉树 AVL

线段树 - Segment Tree

• 线段树
• 懒更新线段树

字典树 - Trie

• 字典树

并查集 - Union Find

• Union Find

树状数组 - Binary Indexed Tree

• 树状数组

字符匹配 - String Match

• 暴力破解法
• Rabin Karp
• KMP

图 - Graph

• 图的数据结构表示

无向无权图

• 深度优先遍历 - DFS
• 连通分量
• 单一路径
• 环检测
• 二分图检测
• 广度优先遍历 - BFS
• 哈密尔顿回路 - 回溯
• 欧拉回路 - Hierholzer 算法

无向有权图

• 最小生成树 - Kruskal 算法 $O(ElogE)$
• 最小生成树 - Prime 算法 $O(ElogE)$
• 迪杰斯特拉 - Dijkstra 算法 $O(ElogE)$
• 贝尔曼福特 - Bellman Ford 算法 $O(VE)$
• 弗洛伊德 - Floyed 算法 $O(V^3)$

其他

• 二分查找 Binay Search
• 前缀和 Pre-Sum