算法

排序

排序算法 平均时间复杂度 最差时间复杂度 空间复杂度 数据对象稳定性
冒泡排序 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\ )

其他算法

算法 思想 应用
分治法 把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并 循环赛日程安排问题、排序算法(快速排序、归并排序)
动态规划 通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法,适用于有重叠子问题和最优子结构性质的问题 背包问题、斐波那契数列
贪心法 一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法 旅行推销员问题(最短路径问题)、最小生成树、哈夫曼编码