当前位置:网站首页>CSDN21天学习挑战赛之折半插入排序
CSDN21天学习挑战赛之折半插入排序
2022-08-10 23:05:00 【进击的博仔】
活动地址:CSDN21天学习挑战赛
“九层之台,起于垒土”。学习技术须脚踏实地。
折半插入排序的概念
插入排序是一种较基础的排序算法,原理也简单易懂,只要会玩扑克就应该能很快学会。
直接插入排序通过构建有序序列,依次扫描无序序列的每个元素,将其与有序序列比较,插入小于自身的元素后面,其余元素依次后移。
折半插入排序是直接插入排序的一个改进版本。由于直接插入排序具有有序序列,所以查找要插入位的置过程可以利用折半查找,减少了元素比较的次数,但元素移动次数并没有改变。
算法描述
- 假设已有 i-1 个元素排好,取出第 i 个元素 temp。
- 通过二分查找该元素应插入的位置 location,即右侧元素小于它,左侧元素大于它。
- 将 location(包括) 后到 i(不包括)的元素依次后移一位。
- 把temp放入location。
- 回到第一步直至 i 等于 n。
C++实现
template<typename T>
void BinaryInsertSort(T* a, int size){
int mid;
for(int i = 1; i < n;i++){
int lo = 0, hi = i - 1;
while(lo <= hi){
mid = lo + (hi - lo)/2;
if(a[i] < a[mid])
hi = mid - 1;
else
lo = mid + 1;
}
int temp=arr[i];
//由折半查找到的正确插入位置为high+1
//将high+1后面的元素依次后移
for(int j=i-1;j>=high+1;j--)
arr[j+1]=arr[j];
arr[high+1]=temp;
}
}
最后一次循环有三种情况:
- lo == hi,a[hi] >= a[mid] 时, hi = mid-1,hi+1 就是 temp 需要插入的位置。
- lo == hi,a[hi] < a[mid] 时, lo = mid+1,hi+1 还是 temp 需要插入的位置。
- hi = lo + 1,a[mid] = a[lo] > a[i]时,hi = mid-1,hi+1 还是 temp 需要插入的位置。
综上 hi+1 就是 temp 需要插入的位置。
复杂度分析
时间复杂度
折半插入只是在查找位置是更加快速了,元素移动次数还是不变的,所以总得来说与直接插入排序处于同一量级,还是 O ( n 2 ) O(n^2) O(n2)。但它的性能是要优于直接插入排序的。
空间复杂度
只需要维护几个索引与一个中间值,所以为 O ( 1 ) O(1) O(1)。
边栏推荐
猜你喜欢
随机推荐
【Linux】宝塔面板设置MySQL慢查询日志,未走索引日志
小程序平台工具如何选择和使用?
北京党建展馆vr全景制作优点有哪些
HGAME 2022 Week1 writeup
CW614N铜棒CuZn39Pb3对应牌号
使用PageHelper自定义PageInfo进行分页+模糊查询
实例049:lambda
二叉树 | 代码随想录学习笔记
腾讯云轻量应用服务器配置及建网站教程
sklearn.datasets.make_circles
国内vr虚拟全景技术领先的公司
二叉树 | 翻转二叉树 | leecode刷题笔记
How to bounce the shell
(PC+WAP)带手机端pbootcms模板园林景观类网站
ITK 读取一个目录中的一个序列,然后改变头信息,将多张dcm图像写成一个dcm文件。
怼不过产品经理?因为你不懂DDD领域建模与架构设计
PlaidCTF 2022 Amongst Ourselves:Shipmate writeup
高学历毕业生,该学单片机还是plc?
确诊了!是Druid1.1.20的锅,查询无法映射LocalDateTime类型(带源码解析及解决方案)
有趣并发性能分享:线程池为什么设计成这样?