【排序算法之插入排序】
2023-04-18 16:51:35 时间
概要:本期主要学习排序算法中的插入排序,会着重讲解算法的核心思想、时空复杂度分析以及代码的实现。
一、插入排序
如何维护一个动态数组有序?只需要将新插入的元素与数组内的其他元素循环比较,将其插入有序位置。参照这种思想,运用在静态数组上,就实现了插入排序的算法。
二、核心思想
插入排序的核心思想就是将数组中所有元素循环与数组中其他元素比较,调整其本身位置,最终达到数组有序的状态。
- 循环遍历每个元素,作为参照元素。
- 用参照元素与数组中其他元素按照升序或者降序循环比较,若出现第一个与比较规则相反的元素,则需要在该元素前插入参照元素。这时需要将该元素后的其余元素后移一位。
- 每个参照元素做完一轮比对后,就可以完成该元素的最终位置的确认。
- 执行n轮后,数组内元素达到有序状态。
三、时空复杂度分析
插入排序的时间复杂度可以从最好、最坏和平均三个层次来分析。
- 最好的情况是数组有序,我们不需要移动数据元素,如果从尾部开始比对,则只需要比对一次就可以确定最终位置。所以,最好情况下的时间复杂度为O(n)。
- 最坏的情况是数组逆序,我们比较需要移动n-1个数据元素,比较n个元素,所以最坏情况下的时间复杂度为O(n^2)。
- 平均的情况下,我们仍然取最好和最坏情况的平均值,需要移动(n-1)/2个元素,比对n个元素后,数组达到有序状态。所以时间复杂度为O(n^2)。
四、代码实现
插入排序和冒泡排序的时间复杂度都为O(n^2),但是插入排序其实比冒泡排序的效果更好,这一点我们需要关注它们在进行数据移动时的代码。
下面展示C++的实现源码:
void SortFuncation::InsertSort(QVector<int> _vec)
{
if(_vec.length() <= 1)
{
return ;
}
QTime _beginTime = QTime::currentTime();
qDebug()<<QString::fromLocal8Bit("开始时间:")<<_beginTime.toString("hh:mm:ss:zzzz");
int _iLen = _vec.length();//记录vector的长度
for(int i = 0;i < _iLen;i ++)
{
int _value = _vec.at(i);
int j = i - 1;
for(j;j >= 0;j --)
{
if(_vec[j] > _value)
{
_vec[j+1] =_vec[j];
}
else
{
break;
}
}
_vec[j+1] = _value;
}
QTime _endTime = QTime::currentTime();
qDebug()<<QString::fromLocal8Bit("结束时间: ")<<_endTime.toString("hh:mm:ss:zzzz");
qDebug()<<QString::fromLocal8Bit("插入排序耗时:")<<_beginTime.msecsTo(_endTime)<<"ms";
}
结尾
本期对于插入排序的学习就到这,下棋我们学习选择排序:)
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击