专攻软考高频算法模块！深度解析二分查找的循环不变量设计、堆排序的建堆/下沉实战推演，重点攻克快速排序的partition优化与复杂度陷阱。横向对比九大排序算法（冒泡/选择/插入/希尔/归并/快排/堆排/计数/桶排）的适用场景，通过12组动画图解揭示堆调整、递归树分裂等核心过程，提炼「哈希冲突避坑指南」「手撕堆排序三步法」「快排最优轴点选择」等硬核技巧，配套20道真题逆向拆解，助考生7天吃透算法模块的45%分值权重，构建从原理推导到考场秒杀的完整知识闭环！

一、查找

1. 静态查找表：

1. 概念：查询表中某个特定的元素或检索某一个特定元素的各种属性
2. 查询方法：顺序查找、折中（二分）查找、分块查找

2. 动态查找表：

1. 概念：需要在查找的表中插入不存在的元素或从表中删除已存在的元素
2. 查询方法：二叉排序树、平衡二叉树、B_树、哈希表

3. 平均查找长度

1. 公式

注意：平均查找长度只有在顺序查找中考过

顺序查找

1. 顺序查找的方法对于顺序存储方式和链式存储方式都适用。
2. 平均查找长度：

1. ASL=（1+n）/2

3. 最多比较次数为n次

折半查找

1. 使用条件

1. 采用顺序存储
2. 递增有序排序

2. 查询步骤：

3. 最多比较次数：
4. 代码截图

5. 查找平均长度：ASL=

折半查找判定数

注意点：遇到除2，除不尽的，优先考虑向下取整。

折半例题

题一：

技巧：假设：最后一位为查找到的值，通过调整比较下标，找错误。

注意关键码可能存在的规律：

大大大大大

小小小小小

大小大小大小

小大小大小大

哈希表

1. 定义：哈希表是通过计算一个以记录的关键字为自变量的函数（称为哈希函数），来得到该记录的存储地址。然后到相应的存储单元去获得有关信息再判定查找是否成功。
2. 如果到k1≠k2，但是 k1和k2通过哈希函数得到的值是相同的，称之为冲突，

1. k1和k2也可以称为同义词

1. 例：k1=4,k2=2,
2. hx（k1）=1,hx(k2)=1

3. 注意：冲突是不可避免的。

哈希表的构造方法

1. 常用的哈希函数构造方法有：

1. 直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法 （考试常考）

2. 在构造哈希函数时，一般都要对关键字进行计算，且尽可能使关键字的所有组成部分都能起作用。（考过   时间：2013年）
3. 构造形式：

1. 如果有n个元素
2. H(key)=key%m=地址
3. m一般取接近n但不大于n的质数   （＜n）  【注意：考过  时间：2013年】

哈希表解决冲突的方法--开放定址法之线性探测法

1. 公式：
2. 公式解释：

3. 例题1：

1. 由题中可以看出，关键码12的地址是冲突的，
2. 所以需要使用开放定址法：h1=(1+1)%11=2（位置2并没有关键码，所以可以存入地址2）

4. 例题2：

5. 例题3：

1. 答案为：b

哈希表解决冲突的方法--开放定址法之二次探测法

增量序列为：1,-1,4,-4,9，-9......

注：使用方法和一次探测法一致，区别为：使用的增量序列不同

哈希表解决冲突的方法--链地址法

1. 遇到两个或两个以上关键码冲突时，直接通过链表将冲突的值链在一起就好了。
2. 例题：

装填因子α

1. α=表中装入的记录数/哈希表的长度

1. 例：哈希表的长度为：10，已经存储元素1个，

1. α=1/10

2. α越小，冲突的可能越小，反之，α越大，表中已填入的元素越多，出现冲突的可能越大。
3. 例题：

1. 答案：b

哈希表概念题

二、堆

概念：n个关键码构成的序列{k1,k2,k3......},当且仅当满足下列关系时称其为堆

小顶堆（小根堆）和大顶堆（大根堆）

构造小顶堆或构造大顶堆

如给出一含n个数值的数组，构造出大根堆，

1. 步骤：

1. 先将数组中的树从上至下，从左至右插入到二叉树中

1. 因为大大根堆的构造条件为ki≥k2i and ki大于等于ki2+1
2. 所以我们只需将每个分支结树的结点交换成比子树大的数即可。

例：

最后将构造好的二叉树：从上至下，从左至右写下来即可。

2. 例题：

三、排序

1. 背

注意：，完全有序列/基本有序在使用直接插入时，时间复杂度为:O（n）

具有归位属性：冒泡、简单选择排序、堆排序、快速排序

修改表格内容：

快速排序的空间复杂度为：n

2. 稳定性：

1. 如果在一个数组中有两个相同的数字，但是在经过排序后，相同数字中的后一个数字还是在后的话，则为稳定，
2. 否则就说明该算法不稳定
3. 例：{3,2,1,2}

1. 经过排序后，{1,2,2,3}  ======》稳定
2. 经过排序后，{1,2,2,3}  ======》 不稳定

3. 内部排序：指待排序的记录全部存放在内存中进行排序的过程
4. 排序分类：

1. 插入：直接、希尔
2. 选择：简单、堆
3. 交换：冒泡、快

排序知识点引入

1. 归位：每进行一次排序，可以将元素放入到最终位置
2. 完全有序：[1,2,3,4]
3. 基本有序：[1,2,4,3]

直接插入排序

1. 直接插入排序是局部有序的，不是全局有序的。
2. 排序步骤：

3. 代码截图：

希尔排序

希尔排序是直接插入排序的优化

1. 思想：

1. 将整个待排记录序列分割成若干个子序列
2. 在分别进行插入排序，到基本有序时，在进行下一次直接排序

2. 步骤：

3. 代码
4. 例题：

计数排序

序列只有（0~9或1~9）的数

冒泡排序

1. 每次循环找到最大的元素
2. 步骤

简单选择排序

1. 每次找出最小的值
2. 排序步骤：

堆排序

1. 大根堆：递增
2. 小根堆：递减
3. 排序步骤：

1. 先将一位数组转成（大/小）根堆
2. 大根堆完成后，转为一维数组，将首项和尾箱交换，并把最后提出，
3. 交换后，对1个元素到n-1元素继续构造成大根堆

4. 例

快速排序

1. 分治思想
2. 步骤：首先找到轴，在将数组分成左（大于轴）右（小于轴），分别进行排序
3. 记：快速排序在基本有序序列中，时间复杂度最高
4. 例题：

例题：

、

归并排序

1. 思想：分治
2. 排序步骤：