数据结构与算法-排序(三)插入排序(Insertion Sort)
2021/8/3 22:07:49
本文主要是介绍数据结构与算法-排序(三)插入排序(Insertion Sort),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
摘要
插入排序是先假定一部分序列是有序的,这部分序列也可以是 0 个元素。另外需要排序的元素就一个个的插入到这个有序的序列中。因为要插入的序列本来就是有序的,所以只要找到合适的插入位置,那么就可以结束这轮循环。
代码中处理的就是界定遍历边界,和减少遍历次数,提高效率。这里的有序序列是元素从左开始,由小到大。
逻辑
这里可以想象扑克牌排序,手中拿着一组由小到大的牌,每次拿起一张牌,就会插入到合适的位置,继续保持由小到大的牌面。
这里提高效率,主要是保持序列的空间长度,在原有的序列中操作,不额外创建新的序列空间。
流程
1、执行过程中,会分为两部分:
- 头部已经排序好的
- 尾部等待排序的
2、从头扫描每一个元素:
- 每当扫描到一个元素,就将它插入到头部合适的位置,依然保持头部有序
- 插入位置的元素序列就统一往后移动
实现
在遍历序列时,会有一个 begin
做界限,begin
之前的序列部分是有序的,后面的部分是无序的。
每一次就是把 begin
位置上的元素插入到有序的部分中,先看代码:
for (int begin = 0; begin < array.length; begin++) { int cur = begin; while (cur > 0 && cmp(cur, cur - 1) < 0) { swap(cur, cur - 1); cur--; } }
代码中有两个继续 while
(插入循环)的条件,第一个是 cur > 0, 防止序列索引越界。
另外一个是 cmp
方法,因为上面说过 begin 之前的序列是有序的,所以当发现一次前一个位置的值小于或等于当前位置的值,那么就可以结束。不可能再出现前一个位置元素大于当前位置元素的情况了。
这就是减少遍历比较的有底气的地方。
进阶
上面代码中可以看到,每发现符合 while
条件的,就交换元素位置,这里就将交换转换为挪动:
- 先备份备份待插入元素
- 头部有序数组中比待插入元素大的,向后移动一位
- 将待插入元素放入到最终合适的位置
for (int begin = 0; begin < array.length; begin++) { int cur = begin; E v = array[cur]; while (cur > 0 && cmp(v, array[cur-1]) < 0) { array[cur] = array[cur-1]; cur--; } array[cur] = v; }
逆序对(Inversion)
逆序对(自己的理解):
在序列中,出现违反有序原则的每一对元素,都是逆序对,这一对元素不需要相邻,这对元素可以被重复和其他元素配对,成为一对新的逆序对,下看面例子
数组 [2,7,4,5,9,8] 的逆序对有 [7,4]、[7,5]、[9,8]
接下来可以思考一下,能影响到插入排序的因素是什么,整体看下来,序列中当发现有逆序对,才进行交换并继续遍历下一个。发现一个不是逆序对的,就结束遍历了。
那么就可以总结,插入排序的时间复杂度和序列中的逆序对的数量成正比。
时间和空间复杂度
- 最坏、平均时间复杂度:O(n^2)
- 最好时间复杂度:O(n)
- 空间复杂度:O(1)
- 属于稳定排序
这篇关于数据结构与算法-排序(三)插入排序(Insertion Sort)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)