记录我想记录的博客
- Linked List 链表
- Doubly Linked List 双向链表
- Queue 队列
- Heap 堆 - 最大堆和最小堆
- Hash Table 哈希表
- stack 栈
- Tree 树
- Binary Search Tree 二叉搜索树
- AVL Tree AVL树
- Red-Black Tree 红黑树
- Segment Tree 线段树
- Fenwick Tree 树状数组
- Graph 图 (有向图与无向图)
- Disjoint Set 并查集
- Bloom Filter 布隆过滤器
| 数据结构 | 连接 | 查找 | 插入 | 删除 | 备注 |
|---|---|---|---|---|---|
| 数组 | 1 | n | n | n | |
| 栈 | n | n | 1 | 1 | |
| 队列 | n | n | 1 | 1 | |
| 链表 | n | n | 1 | 1 | |
| 哈希表 | - | n | n | n | 在完全哈希函数情况下，复杂度是 O(1） |
| 二分查找树 | n | n | n | n | 在平衡树情况下，复杂度是 O(log(n)) |
| B 树 | log(n) | log(n) | log(n) | log(n) | |
| 红黑树 | log(n) | log(n) | log(n) | log(n) | |
| AVL 树 | log(n) | log(n) | log(n) | log(n) | |
| 布隆过滤器 | - | 1 | 1 | - | 存在一定概率的判断错误（误判成存在） |
- 排序 (Sort)
- 冒泡排序 - Bubble Sort
- 选择排序 - Selection Sort
- 插入排序 - Insertion Sort
- 堆排序 - Heap Sort
- 归并排序 - Merge Sort
- 快速排序 - Quick Sort
- 希尔排序 - Shell Sort
- 计数排序 - Counting Sort
- 基数排序
| 名称 | 最优 | 平均 | 最坏 | 内存 | 稳定 | 备注 |
|---|---|---|---|---|---|---|
| 冒泡排序 | n | n^2 | n^2 | 1 | Yes | |
| 插入排序 | n | n^2 | n^2 | 1 | Yes | 如果序列基本有序，则插入排序简单且有效，比冒泡排序效率要高 |
| 选择排序 | n^2 | n^2 | n^2 | 1 | No | |
| 堆排序 | n log(n) | n log(n) | n log(n) | 1 | No | |
| 归并排序 | n log(n) | n log(n) | n log(n) | n | Yes | |
| 快速排序 | n log(n) | n log(n) | n^2 | log(n) | No | 在 in-place 版本下，内存复杂度通常是 O(log(n)) |
| 希尔排序 | n log(n) | 取决于差距序列 | n (log(n))^2 | 1 | No | |
| 计数排序 | n + r | n + r | n + r | n + r | Yes | r - 数组里最大的数 |
| 基数排序 | n * k | n * k | n * k | n + k | Yes | k - 最长 key 的升序 |
- 单例模式 - Singleton Pattern
- 策略模式 - Strategy Pattern
- 代理模式 - Proxy Pattern
- 迭代器模式 - Iterator Pattern
- 发布-订阅模式
- 命令模式
- 组合模式
- 模板模式
- 享元模式
- 责任链模式
- 中介者模式
- 装饰者模式
- 状态模式
- 适配器模式