jjzjj

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

微凉秋意 2024-06-27 原文

活动地址：CSDN21天学习挑战赛

✅作者简介：C/C++领域新星创作者，为C++和java奋斗中
✨个人社区：微凉秋意社区
🔥系列专栏：经典算法
📃推荐一款模拟面试、刷题神器👉注册免费刷题

🔥前言

书接上文，今天带来算法基础中的折半插入排序，一个综合了直接插入排序和二分查找的算法。和以往四篇不同，这篇文章将会加入详细调试的图片，帮助大家理解该算法的流程。本篇文章也将收录在经典算法专栏，此专栏免费且收录经典算法，感兴趣的朋友可订阅以便持续观看。

文章目录

折半插入排序算法解析

一、理解算法思想

  • 每次从原有数据中取出一个数，插入到之前已经排好的序列中，直到所有的数全部取完，该算法过程与直接插入排序算法极为相似，区别就是在插入的时候 高效 的选择位置。
    • 使用二分（折半）查找来选择插入位置

二、算法流程

  1. 外层循环用来找到序列中无序的入口
  2. 进入无序入口后，记录入口位置元素值并进入二分查找
  3. 二分查找结束后，将元素值向依次后覆盖
  4. 最后将入口位置的元素值插入到二分查找结束的位置即可

三、代码实现

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、详细的调试过程

  1. 使用VS编译器，在程序更改序列的的位置设置断点
  2. 启动调试，可以看到程序已经运行到断点处且无错误
  3. 根据上一个调试结果可以看到第一个程序入口位置是 i = 3，二分查找结束的条件是 low >high，那么继续逐语句调试，观察数组中元素值的变化
  4. 上一张图片arr[3]变为了50，随之j--，再次调试的话arr[2]的值也会发生改变
  5. 可以看到arr[2]的值变为45，那么下一次调试将跳出for循环，arr[1]的将变为入口位置的元素值
  6. 那么该入口的折半插入排序就完成了，接下来运行到外层for循环，继续寻找无序入口并重复上面的操作
  7. 上次调试的情况是当i=5时，进入折半排序入口，流程和前五步一致，所以直接看最终调试结果

2、时间复杂度

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

本文到此结束，如有问题务必交流指正，期待你的关注与支持~
​

折半拿捏spanclasstoken排序算法算法c++

有关用调试来帮你分析并拿捏折半插入排序算法的流程的更多相关文章

  1. ruby-on-rails - 无法让 rspec、spork 和调试器正常运行 - 2

    GivenIamadumbprogrammerandIamusingrspecandIamusingsporkandIwanttodebug...mmm...let'ssaaay,aspecforPhone.那么，我应该把“require'ruby-debug'”行放在哪里，以便在phone_spec.rb的特定点停止处理？(我所要求的只是一个大而粗的箭头，即使是一个有挑战性的程序员也能看到:-3)我已经尝试了很多位置，除非我没有正确测试它们，否则会发生一些奇怪的事情:在spec_helper.rb中的以下位置:require'rubygems'require'spork'

  2. ruby - JetBrains RubyMine 3.2.4 调试器不工作 - 2

    使用Ruby1.9.2运行IDE提示说需要gemruby​​-debug-base19x并提供安装它。但是，在尝试安装它时会显示消息Failedtoinstallgems.Followinggemswerenotinstalled:C:/ProgramFiles(x86)/JetBrains/RubyMine3.2.4/rb/gems/ruby-debug-base19x-0.11.30.pre2.gem:Errorinstallingruby-debug-base19x-0.11.30.pre2.gem:The'linecache19'nativegemrequiresinstall

  3. ruby-on-rails - 如何调试 cucumber 测试？ - 2

    我有:When/^(?:|I)follow"([^"]*)"(?:within"([^"]*)")?$/do|link,selector|with_scope(selector)doclick_link(link)endend我打电话的地方:Background:GivenIamanexistingadminuserWhenIfollow"CLIENTS"我的HTML是这样的:CLIENTS我一直收到这个错误:.F-.F--U-----U(::)failedsteps(::)nolinkwithtitle,idortext'CLIENTS'found(Capybara::Element

  4. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  5. ruby - Ruby 是否有类似于 Perl 的 "perl -d"的逐步调试器？ - 2

    Ruby是否有逐步调试器，类似于Perl的“perl-d”？ 最佳答案 ruby-debug(对于ruby1.8)，debugger(对于ruby1.9)，byebug(对于ruby​​2.0)以及trepanning系列都有一个-x或--trace选项。在调试器内部，命令setlinetrace将打开或关闭线路跟踪。这是themanualforruby-debug原来的答案已经修改，因为数据噪声文章的链接，唉，不再有效了。还添加了ruby​​-debug的后继者 关于ruby-Ruby

  6. ruby-on-rails - 需要帮助最大化多个相似对象中的 3 个因素并适当排序 - 2

    我需要用任何语言编写一个算法，根据3个因素对数组进行排序。我以度假村为例(如Hipmunk)。假设我想去度假。我想要最便宜的地方、最好的评论和最多的景点。但是，显然我找不到在所有3个中都排名第一的方法。Example(assumingthereare20importantattractions):ResortA:$150/night...98/100infavorablereviews...18of20attractionsResortB:$99/night...85/100infavorablereviews...12of20attractionsResortC:$120/night

  7. ruby - 如何在 Ruby 字符串中插入项目符号字符？ - 2

    我正在尝试创建一个带有项目符号字符的Ruby1.9.3字符串。str="•"+"helloworld"但是，当我输入它时，我收到有关非ASCII字符的语法错误。我该怎么做？ 最佳答案 你可以把Unicode字符放在那里。str="\u2022"+"helloworld" 关于ruby-如何在Ruby字符串中插入项目符号字符？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/1195

  8. ruby-on-rails - 在具有 ActiveRecord 条件的相关模型中按字段排序 - 2

    我正在尝试按Rails相关模型中的字段进行排序。我研究的所有解决方案都没有解决如果相关模型被另一个参数过滤？元素模型classItem相关模型:classPriority我正在使用where子句检索项目:@items=Item.where('company_id=?andapproved=?',@company.id,true).all我需要按相关表格中的“位置”列进行排序。问题在于，在优先级模型中，一个项目可能会被多家公司列出。因此，这些职位取决于他们拥有的company_id。当我显示项目时，它是针对一个公司的，按公司内的职位排序。完成此任务的正确方法是什么？感谢您的帮助。PS-我

  9. ruby - 按数字(从大到大)然后按字母(字母顺序)对对象集合进行排序 - 2

    我正在构建一个小部件来显示奥运会的奖牌数。我有一个“国家”对象的集合，其中每个对象都有一个“名称”属性，以及奖牌计数的“金”、“银”、“铜”。列表应该排序:1.首先是奖牌总数2.如果奖牌相同，按类型分割(金>银>铜，即2金>1金+1银)3.如果奖牌和类型相同，则按字母顺序子排序我正在用ruby​​做这件事，但我想语言并不重要。我确实找到了一个解决方案，但如果感觉必须有更优雅的方法来实现它。这是我做的:使用加权奖牌总数创建一个虚拟属性。因此，如果他们有2个金牌和1个银牌，加权总数将为“3.020100”。1金1银1铜为“3.010101”由于我们希望将奖牌数排序为最高的，因此列表按降序排

  10. ruby - 在 ruby​​ 中使用自动创建插入数组 - 2

    我想知道是否可以通过自动创建数组来插入数组，如果数组不存在的话，就像在PHP中一样:$toto[]='titi';如果尚未定义$toto，它将创建数组并将“titi”压入。如果已经存在，它只会推送。在Ruby中我必须这样做:toto||=[]toto.push('titi')可以一行完成吗？因为如果我有一个循环，它会测试“||=”，除了第一次:Person.all.eachdo|person|toto||=[]#with1billionofperson,thislineisuseless999999999times...toto.push(person.name)你有更好的解决方案吗？

随机推荐