排序
1. 主存能放下的数据进行排序称为内部排序, 反之称为外部排序 (磁盘上)
2. 任何进行交换相邻元素进行排序的算法均需要 O(N2) 的复杂度, 任何进行比较的排序算法至少需要 O(N*log(N)) 的算法复杂度
3. 堆排序和归并排序的时间复杂度平均和最坏均为 O(N*log(N))
4.Java 中执行一次对象比较是比较昂贵的, 移动则是相对节省的, 因此归并排序是 java 的默认泛型排序算法 C++ 中默认的是快速排序, 比较耗费小; 快排对于基本类型均具有最快速度快速排序选取枢纽元的时候采用三数取中, 切勿采用首元素
5. 桶排序: 排序的数小于整数 M, 实例化一个 M 维的数组初值为 0, 依次加入桶, 再倒回去
6. 基数排序: 排序数组有 n 个元素, 实例化一个包含 10 个 list 的数组 (相当于 n 个桶 0123456789), 依次从个位数到最高位把 n 个数放入桶中然后再倒回原数组, 每次要清空 list
适合字符串的排序
图论算法
1. 定义:
(1) 图由顶点和边组成 G=(V,E), 分为有向图和无向图; 边可以有一定权重, 边也称为度有向无圈图也称为 DAG
(2) 图是稠密的考虑用邻接矩阵表示 O(V2); 稀疏图一般用邻接表表示 O(E+V)
2. 拓扑排序: 是对有向无圈图的一种排序方式, 使得如果存在一条从 vi 到 vj 的路径, 那么在排序中 vj 就出现在 vi 的后面 (先找出没有入边的顶点)
3 最短路径算法:
单源最短路径问题: 给定顶点, 到任意其他顶点的最短距离的算法 O(V+E):(即为广度优先搜索 breadth-first search)
来源: http://www.bubuko.com/infodetail-2514791.html