排序算法与查找算法
1.十大经典排序算法
我们希望数据以一种有序的形式组织起来，无序的数据我们要尽量将其变得有序
一般说来有10种比较经典的排序算法
简单记忆为Miss D----D小姐
时间复杂度 ：红色<绿色<蓝色
空间复杂度：圆越大越占空间
稳定性：虚线不稳(4种）
性能分析
2.常见的查找算法
1.顺序查找
- 时间复杂度O(n)
2.二分查找
- 时间复杂度O(logN)
- 要求：1）有序；2）支持下标的随机访问
3.二叉搜索树(BS树)
- 时间复杂度O(logN)
- 若接近有序的数据插入到BS中，会导致退化成单支树，时间复杂度退化为O(N)
4.平衡搜索树(AVL树和RB树)
- 时间复杂度O(logN)
- 在BS的基础上，通过一些规则加以限制，通过旋转来限制高度，维持logN的时间复杂度
5.哈希查找
- 时间复杂度O(1)
- 底层是散列表，要注意解决哈希冲突。
- 综合效率优于平衡搜索树
6.多路平衡搜索树(B树和B*树)
- 解决大数据量问题，如磁盘定位
- B树的改进版本B+树、B*树，有些地方的B树写的是B-树，不要误读成“B减树”