算法
优质
小牛编辑
133浏览
2023-12-01
排序
| 排序算法 | 平均时间复杂度 | 最差时间复杂度 | 空间复杂度 | 数据对象稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n2) | O(1) | 稳定 |
| 选择排序 | O(n2) | O(n2) | O(1) | 数组不稳定、链表稳定 |
| 插入排序 | O(n2) | O(n2) | O(1) | 稳定 |
| 快速排序 | O(n*log2n) | O(n2) | O(log2n) | 不稳定 |
| 堆排序 | O(n*log2n) | O(n*log2n) | O(1) | 不稳定 |
| 归并排序 | O(n*log2n) | O(n*log2n) | O(n) | 稳定 |
| 希尔排序 | O(n*log2n) | O(n2) | O(1) | 不稳定 |
| 计数排序 | O(n+m) | O(n+m) | O(n+m) | 稳定 |
| 桶排序 | O(n) | O(n) | O(m) | 稳定 |
| 基数排序 | O(k*n) | O(n2) | 稳定 |
- 均按从小到大排列
- k：代表数值中的 “数位” 个数
- n：代表数据规模
- m：代表数据的最大值减最小值
- 来自：wikipedia . 排序算法
查找
| 查找算法 | 平均时间复杂度 | 空间复杂度 | 查找条件 |
|---|---|---|---|
| 顺序查找 | O(n) | O(1) | 无序或有序 |
| 二分查找（折半查找） | O(log2n) | O(1) | 有序 |
| 插值查找 | O(log2(log2n)) | O(1) | 有序 |
| 斐波那契查找 | O(log2n) | O(1) | 有序 |
| 哈希查找 | O(1) | O(n) | 无序或有序 |
| 二叉查找树（二叉搜索树查找） | O(log2n) | ||
| 红黑树 | O(log2n) | ||
| 2-3树 | O(log2n - log3n) | ||
| B树/B+树 | O(log2n) |
图搜索算法
| 图搜索算法 | 数据结构 | 遍历时间复杂度 | 空间复杂度 |
|---|---|---|---|
| BFS广度优先搜索 | 邻接矩阵 邻接链表 | O(|v|2) O(|v|+|E|) | O(|v|2) O(|v|+|E|) |
| DFS深度优先搜索 | 邻接矩阵 邻接链表 | O(|v|2) O(|v|+|E|) | O(|v|2) O(|v|+|E|) |
其他算法
| 算法 | 思想 | 应用 |
|---|---|---|
| 分治法 | 把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并 | 循环赛日程安排问题、排序算法（快速排序、归并排序） |
| 动态规划 | 通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法，适用于有重叠子问题和最优子结构性质的问题 | 背包问题、斐波那契数列 |
| 贪心法 | 一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法 | 旅行推销员问题（最短路径问题）、最小生成树、哈夫曼编码 |