嵌入式day41
哈希表
将要存储的数据的关键字和位置建立对应的关系，通过哈希函数（散列函数）将数据映射到存储的位置，方便快速查找
哈希冲突/哈希矛盾：
key1 != key2
f(key1) = f(key2)
解决方法：
链地址法
算法
解决特定问题求解步骤
算法的设计：
1.正确性
语法正确
合法的输入能得到合理的结果
对非法的输入，给出满足要求的规格说明
对精心选择，甚至刁难的测试都能正常运行，结果正确
2.可读性，便于交流，阅读，理解 高内聚 低耦合
3.健壮性，输入非法数据，能进行相应的处理，而不是产生异常
4.高效率（时间复杂度）
5.第存储（空间复杂度）
算法时间复杂度
执行这个算法所花时间的度量
将数据量增长和时间增长用函数表示出来，这个函数就叫做时间复杂度
一般用大O表示法：O（n）--- 时间复杂度是关于数据n的一个函数
随着n的增加，时间复杂度增长较慢的算法时间复杂度低
时间复杂度的计算规则
1.用常数1 取代运行时间中的所有加法常数
2.在修改后的运行函数中，只保留最高阶项
3.如果最高阶存在且系数不是1，则去除这个项相乘的常数
排序算法：
稳定性：相同数据，排序后
冒泡：
思想：相邻数据两两比较，小的放前，大的放后
代码：
时间复杂度：O（n^2）
排序算法的稳定性：稳定
选择：
思想：待排数据与后面数据依次比较，将数据放在合适的位置
代码：
时间复杂度：O（n^2）
稳定性：不稳定
插入：
思想：将待排的数据插入到已有的数据中的合适的位置
代码：
时间复杂度：O（n^2）
稳定性：稳定
快速排序：
思想：先设置基准数（begin），从右往左找，第一个比基准数小的数，从左往右找，第一个比基准数大的数，互换两个数，重复刚才的操作，直到p ，q 相遇，内层循环结束后，将p，q所指的元素与基准数交换
代码：
时间复杂度：O（n log n）
稳定性：不稳定
二分查找（折半查找法）：
序列必须有序
时间复杂度：O（log n）