day06 1.算法的相关概念2.排序算法3.查找算法

程序 = 数据结构 + 算法 算法是程序设计的灵魂，结构是程序设计的肉体 算法：计算机解决问题的方法或步骤

1.1 算法的特性

• 1> 确定性：算法中每一条语句都有确定的含义，不能模棱两可

• 2> 有穷性：程序执行一段时间后会自动结束

• 3> 输入：至少有零个或多个输入

• 4> 输出：至少一个或多个输出

• 5> 可行性：经济可行性、社会可行性、能够运行

1.2 算法的设计要求

• 1> 正确性：给定合理的输入数据，能够得到正确的结果

• 2> 健壮性：对于给定的不合理的输入数据，能够给出相应的处理措施

• 3> 可读性：程序核心代码写注释、程序代码有缩进、程序代码命名规范

• 4> 高效率：要求时间复杂度要尽可能低

• 5> 低存储：要求空间复杂度尽可能低

1.3 时间复杂度

• 1> 算法时间复杂度计算公式：T(n) = O(f(n)); T(n):时间复杂度 n:表示问题的规模 f(n) :是问题规模与执行次数之间的函数 O(f(n)):使用O阶记法，记录算法时间复杂

2.1 排序算法的分类

• 1> 交换类排序：冒泡排序、快速排序

• 2> 选择类排序：简单选择排序、堆排序

• 3> 插入类排序：直接插入排序、折半插入排序

• 4> 归并排序：二路归并、多路归并

2.2 冒泡排序

• 1> 在排序过程中，越大（小）的数据，经由交换后，会慢慢的“浮”到顶端，如同气泡一样

2.3 选择排序

• 1> 概念：每次从待排序序列中，找到最大（小）值，将其与待排序序列的第一个进行交换 1、从待排序序列中选择最值

• 2、如果最值不是待排序序列的第一个，则进行交换

• 3、从剩余待排序序列中，继续重复前两次的操作，直到，待排序序列为空

2.4 直接插入排序

• 1> 每次从待排序序列中，选择第一个，将其插入到已排序序列中

• 1、选取待排序序列中的第一个元素

• 2、跟前面的元素依次比较，如果前面的比当前元素大（小），则将前面的元素后移一位

• 3、直到出现前面的不比当前的大（小）或者已经到最前面了，将选取的元素，放入空位置上

• 4、对于待排序序列中的所有元素，重复上述操作

2.5 快速排序

• 1> 概念：快速排序是在序列元素与选定基准元素比较分割为大小两部分的交换排序

• 从待排序列中任取一个基准元素 与基准元素比较将待排序列分割为大小两部分 再对各部分重新选择基准元素并依此规则排序 直到每个部分只剩一个元素为止

3.1 概念

• 所谓查找，就是给定数据元素的某个值，在查找表中确定一个其关键字等于给定值的数据元素的操作，叫做查找

3.2 查找的分类

• 1> 顺序查找：将待查找数据，进行全部遍历一遍，直到找到要查找的元素

• 2> 折半查找：每次都去除一半的查找范围的查找方式，叫做折半查找

• 3> 哈希查找：利用哈希表和哈希函数完成的查找方式（效率最高）

3.3 折半查找

• 1.要求：在顺序表中进行查找 且 数据必须是有序的

• 2.原理：在顺序存储的有序列表中，通过逐次减半查找范围

3.4 哈希查找

• 1、哈希表是借助哈希函数将序列存储于连续存储空间的查找表

• 2、哈希函数是根据关键字确定存储位置的函数

• 3、哈希冲突是不同关键字由哈希函数得到相同存储位置的现象

• 4、构造哈希函数的方法： 直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法

• 5、除留余数法：取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址的方法 序列长度n：待查找数据的个数 哈希表表长m:一般为大于n的值， n / (3/4) 要被除的值p: 小于或等于表长的最大素数

• 6、解决哈希冲突的方法 开放定址法、线性探测法、二次探测法、伪随机探测法、再哈希法、链地址法、建立公共溢出区