50|折半插入、2路插入、表插入:3种插入类排序类排序有哪些异同?
王健伟
你好,我是王健伟。
在插入类排序中,除了我们以往学习过的直接插入排序和希尔排序之外,比较重点的还有折半插入排序、2 路插入排序和表插入排序。考虑到在面试中,这几种插入类排序的出现频率与直接插入排序、希尔排序相比要低一些,也为了防止你一直学习各种排序算法感觉太枯燥,所以我将它们放到了后面这里来讲解。
这节课,我们就专注理解这三种排序算法。
折半(二分)插入排序(Binary Insertion Sort)
前面我们学习的直接插入排序,是将一个待插入数据与一个已经排好序的序列中的数据进行逐个比较来确定插入数据的位置。
其实,我们完全可以用折半查找(Binary Search,也叫二分查找)的方式找到应该插入的位置,而后再移动元素。如图 1 所示。
图1 折半插入排序示意图
在图 1 中,元素 1、16、23、45、99 已经排好序了。现在,即将对元素 2 进行排序。如果按以往的直接插入排序算法进行排序,2 要依次和 99、45、23、16、1 比较,直至发现值比 1 大,才算找到了自己的插入位置应该为下标为[1]的位置。而且每次比较时还要进行元素的移动操作,比如元素 99 要移动到[5]位置,45 要移动到[4]位置,23 要移动到[3]位置 16 要移动到[2]位置。
而对于折半插入排序,指的是在已经排好序的序列(有序区)中,使用折半查找的方式去确定待排序元素的插入位置。看一看如果即将对元素 2 进行排序,是怎样操作的呢?
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文介绍了折半插入排序、2路插入排序和表插入排序三种插入类排序算法。折半插入排序通过减少待排序元素的比较次数来提高效率,2路插入排序则旨在减少记录的移动次数,需要额外的辅助数组空间。而表插入排序则通过修改指针值代替移动记录,实现在排序过程中不移动记录。虽然这些算法各有特点,但它们的时间复杂度均为O($n^{2}$),空间复杂度为O(n),并且都属于稳定排序算法。总体而言,这些排序算法体现了空间换时间的编程思想,以提高算法执行效率。读者可以通过本文详细的算法步骤和实现代码,深入了解这些排序算法的特点和实现方式。
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《快速上手 C++ 数据结构与算法》,新⼈⾸单¥68
《快速上手 C++ 数据结构与算法》,新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示,欢迎踊跃留言。
收起评论