用调试来帮你分析并拿捏折半插入排序算法的流程

简介: 用调试来帮你分析并拿捏折半插入排序算法的流程

折半插入排序算法解析


一、理解算法思想


每次从原有数据中取出一个数,插入到之前已经排好的序列中,直到所有的数全部取完,该算法过程与直接插入排序算法极为相似,区别就是在插入的时候 高效 的选择位置。

使用二分(折半)查找来选择插入位置


二、算法流程


外层循环用来找到序列中无序的入口

进入无序入口后,记录入口位置元素值并进入二分查找

二分查找结束后,将元素值向依次后覆盖

最后将入口位置的元素值插入到二分查找结束的位置即可


三、代码实现


1、源代码


int main(void)
{
  int arr[6] = { 27,45,50,35,66,32 };
  int len = sizeof(arr) / sizeof(arr[0]);
  cout << "排序前:" << endl;
  for (int i = 0; i < len; i++) {
  cout << arr[i] << " ";
  }
  cout << endl;
  for (int i = 1; i < len ; i++)
  {
  if (arr[i] < arr[i - 1])
  {
    int temp = arr[i]; 
    int low = 0;
    int high = i - 1;  
    while (low <= high) {
    int middle = (low + high) / 2;
    if (temp < arr[middle])
    {
      high = middle - 1;
    }
    else
    {
      low = middle + 1;
    }
    }
    for (int j = i - 1; j >= high + 1; j--)
    {
    arr[j + 1] = arr[j];
    }
    arr[high + 1] = temp;
  }
  }
  cout << "排序后:" << endl;
  for (int i = 0; i < len; i++) {
  cout << arr[i] << " ";
  }
}


解析:


由于不会出现重复元素,所以最后一定会将搜索区间缩小至low与high重合(左右区间端点不断移动)。在最后一次循环时,low、high的值相同,在比较完成后,左右端点发生交错,相差为1,此时要选择一个变量的值作为新插入元素的位置参照。


需要明确的是,在左右端点重合之前,待插入元素必定是能够落在low与high的区间内的,这就决定了tmp一定大于low对应的元素,小于high对应的元素。


而且最终的插入位置应该放在最后比较元素的后一个位置,也就是mid对应位置的后面,所以是mid+1。如果用low表示,就刚好是low,如果用high表示,则是high+ 1。


2、运行效果



四、调试程序,分析算法流程


1、详细的调试过程


使用VS编译器,在程序更改序列的的位置设置断点



启动调试,可以看到程序已经运行到断点处且无错误



根据上一个调试结果可以看到第一个程序入口位置是 i = 3,二分查找结束的条件是 low >high,那么继续逐语句调试,观察数组中元素值的变化



上一张图片arr[3]变为了50,随之j--,再次调试的话arr[2]的值也会发生改变



可以看到arr[2]的值变为45,那么下一次调试将跳出for循环,arr[1]的将变为入口位置的元素值



那么该入口的折半插入排序就完成了,接下来运行到外层for循环,继续寻找无序入口并重复上面的操作



上次调试的情况是当i=5时,进入折半排序入口,流程和前五步一致,所以直接看最终调试结果




2、时间复杂度


对于折半插入排序来说,元素的串位次数没有并发生变化,只是在查找位置是更加快速了,因此该算法与直接插入排序处于同一量级。不过在数据量很大时,要优于直接插入排序,时间复杂度仍为O(n 2 n^2n

2

)

目录
打赏
0
0
0
0
88
分享
相关文章
DeepLearning.ai学习笔记(二)改善深层神经网络:超参数调试、正则化以及优化--Week2优化算法
1. Mini-batch梯度下降法 介绍 假设我们的数据量非常多,达到了500万以上,那么此时如果按照传统的梯度下降算法,那么训练模型所花费的时间将非常巨大,所以我们对数据做如下处理: 如图所示,我们以1000为单位,将数据进行划分,令\(x^{\{1\}}=\{x^{(1)},x^{(2)}……x^{(5000)}\}\), 一般地用\(x^{\{t\}},y^{\{t\}}\)来表示划分后的mini-batch。
975 0
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
108 68
室内障碍物射线追踪算法matlab模拟仿真
### 简介 本项目展示了室内障碍物射线追踪算法在无线通信中的应用。通过Matlab 2022a实现,包含完整程序运行效果(无水印),支持增加发射点和室内墙壁设置。核心代码配有详细中文注释及操作视频。该算法基于几何光学原理,模拟信号在复杂室内环境中的传播路径与强度,涵盖场景建模、射线发射、传播及接收点场强计算等步骤,为无线网络规划提供重要依据。
基于改进遗传优化的BP神经网络金融序列预测算法matlab仿真
本项目基于改进遗传优化的BP神经网络进行金融序列预测,使用MATLAB2022A实现。通过对比BP神经网络、遗传优化BP神经网络及改进遗传优化BP神经网络,展示了三者的误差和预测曲线差异。核心程序结合遗传算法(GA)与BP神经网络,利用GA优化BP网络的初始权重和阈值,提高预测精度。GA通过选择、交叉、变异操作迭代优化,防止局部收敛,增强模型对金融市场复杂性和不确定性的适应能力。
184 80
基于GA遗传优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真
本项目基于MATLAB2022a实现时间序列预测,采用CNN-GRU-SAM网络结构。卷积层提取局部特征,GRU层处理长期依赖,自注意力机制捕捉全局特征。完整代码含中文注释和操作视频,运行效果无水印展示。算法通过数据归一化、种群初始化、适应度计算、个体更新等步骤优化网络参数,最终输出预测结果。适用于金融市场、气象预报等领域。
基于GA遗传优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真
|
21天前
|
基于龙格库塔算法的锅炉单相受热管建模与matlab数值仿真
本设计基于龙格库塔算法对锅炉单相受热管进行建模与MATLAB数值仿真,简化为喷水减温器和末级过热器组合,考虑均匀传热及静态烟气处理。使用MATLAB2022A版本运行,展示自编与内置四阶龙格库塔法的精度对比及误差分析。模型涉及热传递和流体动力学原理,适用于优化锅炉效率。
基于分块贝叶斯非局部均值优化(OBNLM)的图像去噪算法matlab仿真
本项目基于分块贝叶斯非局部均值优化(OBNLM)算法实现图像去噪,使用MATLAB2022A进行仿真。通过调整块大小和窗口大小等参数,研究其对去噪效果的影响。OBNLM结合了经典NLM算法与贝叶斯统计理论,利用块匹配和概率模型优化相似块的加权融合,提高去噪效率和保真度。实验展示了不同参数设置下的去噪结果,验证了算法的有效性。
基于SA模拟退火优化算法的TSP问题求解matlab仿真,并对比ACO蚁群优化算法
本项目基于MATLAB2022A,使用模拟退火(SA)和蚁群优化(ACO)算法求解旅行商问题(TSP),对比两者的仿真时间、收敛曲线及最短路径长度。SA源于金属退火过程,允许暂时接受较差解以跳出局部最优;ACO模仿蚂蚁信息素机制,通过正反馈发现最优路径。结果显示SA全局探索能力强,ACO在路径优化类问题中表现优异。
基于遗传优化的双BP神经网络金融序列预测算法matlab仿真
本项目基于遗传优化的双BP神经网络实现金融序列预测,使用MATLAB2022A进行仿真。算法通过两个初始学习率不同的BP神经网络(e1, e2)协同工作,结合遗传算法优化,提高预测精度。实验展示了三个算法的误差对比结果,验证了该方法的有效性。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等