排序算法与查找算法

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减树”