软考算法破壁战:从二分查找到堆排序,九大排序核心速通指南

本文涉及的产品
多模态交互后付费免费试用,全链路、全Agent
简介: 专攻软考高频算法,深度解析二分查找、堆排序、快速排序核心技巧,对比九大排序算法,配套动画与真题,7天掌握45%分值模块。

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

一、查找

  1. 静态查找表:
  1. 概念:查询表中某个特定的元素或检索某一个特定元素的各种属性
  2. 查询方法:顺序查找、折中(二分)查找、分块查找
  1. 动态查找表:
  1. 概念:需要在查找的表中插入不存在的元素或从表中删除已存在的元素
  2. 查询方法:二叉排序树、平衡二叉树、B_树、哈希表
  1. 平均查找长度
  1. 公式

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

顺序查找

  1. 顺序查找的方法对于顺序存储方式和链式存储方式都适用。
  2. 平均查找长度:
  1. ASL=(1+n)/2
  1. 最多比较次数为n次

折半查找

  1. 使用条件
  1. 采用顺序存储
  2. 递增有序排序
  1. 查询步骤:

  1. 最多比较次数:
  2. 代码截图

  1. 查找平均长度:ASL=

折半查找判定数

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

折半例题

题一:

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

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

大大大大大

小小小小小

大小大小大小

小大小大小大

哈希表

  1. 定义:哈希表是通过计算一个以记录的关键字为自变量的函数(称为哈希函数),来得到该记录的存储地址。然后到相应的存储单元去获得有关信息再判定查找是否成功。
  2. 如果到k1≠k2,但是 k1和k2通过哈希函数得到的值是相同的,称之为冲突
  1. k1和k2也可以称为同义词
  1. 例:k1=4,k2=2,
  2. hx(k1)=1,hx(k2)=1
  1. 注意:冲突是不可避免的。

哈希表的构造方法

  1. 常用的哈希函数构造方法有:
  1. 直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法 (考试常考)
  1. 在构造哈希函数时,一般都要对关键字进行计算,且尽可能使关键字的所有组成部分都能起作用。(考过   时间:2013年)
  2. 构造形式:
  1. 如果有n个元素
  2. H(key)=key%m=地址
  3. m一般取接近n但不大于n的质数   (<n)  【注意:考过  时间:2013年】

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

  1. 公式:
  2. 公式解释:

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

  1. 例题2:

  1. 例题3:
  1. 答案为:b

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

增量序列为:1,-1,4,-4,9,-9......

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

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

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

装填因子α

  1. α=表中装入的记录数/哈希表的长度
  1. 例:哈希表的长度为:10,已经存储元素1个,
  1. α=1/10
  1. α越小,冲突的可能越小,反之,α越大,表中已填入的元素越多,出现冲突的可能越大。
  2. 例题:
  1. 答案:b

哈希表概念题

二、堆

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

小顶堆(小根堆)和大顶堆(大根堆)

构造小顶堆或构造大顶堆

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

  1. 步骤:
  1. 先将数组中的树从上至下,从左至右插入到二叉树中
  1. 因为大大根堆的构造条件为ki≥k2i and ki大于等于ki2+1
  2. 所以我们只需将每个分支结树的结点交换成比子树大的数即可。

例:

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

  1. 例题:

三、排序

注意:,完全有序列/基本有序在使用直接插入时,时间复杂度为:O(n)

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

修改表格内容:

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

  1. 稳定性:
  1. 如果在一个数组中有两个相同的数字,但是在经过排序后,相同数字中的后一个数字还是在后的话,则为稳定,
  2. 否则就说明该算法不稳定
  3. 例:{3,2,1,2}
  1. 经过排序后,{1,2,2,3}  ======》稳定
  2. 经过排序后,{1,2,2,3}  ======》 不稳定
  1. 内部排序:指待排序的记录全部存放在内存中进行排序的过程
  2. 排序分类:
  1. 插入:直接、希尔
  2. 选择:简单、堆
  3. 交换:冒泡、快

排序知识点引入

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

直接插入排序

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

  1. 代码截图:

希尔排序

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

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

  1. 代码
  2. 例题:

计数排序

序列只有(0~9或1~9)的数

冒泡排序

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

简单选择排序

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

堆排序

  1. 大根堆:递增
  2. 小根堆:递减
  3. 排序步骤:
  1. 先将一位数组转成(大/小)根堆
  2. 大根堆完成后,转为一维数组,将首项和尾箱交换,并把最后提出,
  3. 交换后,对1个元素到n-1元素继续构造成大根堆

快速排序

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

例题:

归并排序

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

目录
相关文章
|
17天前
|
机器学习/深度学习 算法 安全
【无人机三维路径规划】基于非支配排序的鲸鱼优化算法NSWOA与多目标螳螂搜索算法MOMSA求解无人机三维路径规划研究(Matlab代码实现)
【无人机三维路径规划】基于非支配排序的鲸鱼优化算法NSWOA与多目标螳螂搜索算法MOMSA求解无人机三维路径规划研究(Matlab代码实现)
|
19天前
|
机器学习/深度学习 运维 算法
基于非支配排序遗传算法NSGAII的综合能源优化调度(Matlab代码实现)
基于非支配排序遗传算法NSGAII的综合能源优化调度(Matlab代码实现)
145 0
基于非支配排序遗传算法NSGAII的综合能源优化调度(Matlab代码实现)
|
19天前
|
机器学习/深度学习 算法 安全
【无人机三维路径规划】多目标螳螂搜索算法MOMSA与非支配排序的鲸鱼优化算法NSWOA求解无人机三维路径规划研究(Matlab代码实现)
【无人机三维路径规划】多目标螳螂搜索算法MOMSA与非支配排序的鲸鱼优化算法NSWOA求解无人机三维路径规划研究(Matlab代码实现)
|
15天前
|
供应链 算法 Java
【柔性作业车间调度问题FJSP】基于非支配排序的多目标小龙虾优化算法求解柔性作业车间调度问题FJSP研究(Matlab代码实现)
【柔性作业车间调度问题FJSP】基于非支配排序的多目标小龙虾优化算法求解柔性作业车间调度问题FJSP研究(Matlab代码实现)
|
12天前
|
机器学习/深度学习 算法 安全
【无人机三维路径规划】基于非支配排序的鱼鹰优化算法NSOOA求解无人机三维路径规划研究(Matlab代码实现)
【无人机三维路径规划】基于非支配排序的鱼鹰优化算法NSOOA求解无人机三维路径规划研究(Matlab代码实现)
|
12天前
|
存储 编解码 算法
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
|
15天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
103 1
|
14天前
|
传感器 机器学习/深度学习 算法
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)
|
12天前
|
机器学习/深度学习 传感器 算法
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
105 14
|
16天前
|
传感器 算法 数据挖掘
基于协方差交叉(CI)的多传感器融合算法matlab仿真,对比单传感器和SCC融合
基于协方差交叉(CI)的多传感器融合算法,通过MATLAB仿真对比单传感器、SCC与CI融合在位置/速度估计误差(RMSE)及等概率椭圆上的性能。采用MATLAB2022A实现,结果表明CI融合在未知相关性下仍具鲁棒性,有效降低估计误差。
131 15