文档章节

直接插入排序

JiaChang
 JiaChang
发布于 2016/08/13 09:25
字数 402
阅读 3
收藏 0

直接插入排序

算法思路

对于一个有 n 个元素的数据序列,排序需要进行 n-1 趟插入操作

第一趟插入:将第2个元素插入到前面的有序子序列中,此时前面只有一个元素,当然是有序的。

第二趟插入:将第3个元素插入到前面的有序子序列中,前面两个元素是有序的。

......

第n-1趟插入:将第n个元素插入到前面的有序子序列中,前面n-1个元素是有序的。

直接插入排序的实现

/***
	 * 直接插入排序
	 * @param data 待排序的数组
	 */
	public static void insertSort(int[] data){
		
		for(int i = 1; i<data.length; i++){
			//如果 i索引前面的元素比 i索引处的元素大,则需要往前插入
			if(data[i-1] > data[i]){
				//当数据整体后移时,保证data[i]处的元素不丢失
				int temp = data[i];
				//最多后移多少个元素
				int j = i-1;
				//循环判断,只要前面的元素比data[i]大,则需要后移
				for(; j>=0 && data[j]>temp; j--){
					data[j+1] = data[j];
				}
				//最后将data[i]插入到合适的位置
				data[j+1] = temp;
			}
		}
	}

测试代码
 

算法分析

(1)时间复杂度:O(n2)(注:这里是n的平方,由于编辑器的原因打不出来)

(2)空间复杂度:O(1)

(3)直接插入排序是稳定的

(4)更适合于初始记录基本有序(正序)的情况,当初始记录无序,n较大时,此算法的时间复杂度较高,不宜采用。

 

© 著作权归作者所有

共有 人打赏支持
下一篇: 快速排序
JiaChang
粉丝 2
博文 32
码字总数 18002
作品 0
海口
程序员
私信 提问

暂无文章

图形用户界面和交互输入方法---图形数据的输入功能

图形数据的输入功能 输入模式 回显反馈

中国龙-扬科
19分钟前
1
0
互联网企业安全之端口监控

背景 外网端口监控系统是整个安全体系中非常重要的一环,它就像眼睛一样,时刻监控外网端口开放情况,并且在发现高危端口时能够及时提醒安全、运维人员做出相应处理。 对安全人员来说,互联网...

Skqing
22分钟前
1
0
JavaMonitor

常规监控jvm,都是比较麻烦的。但是今天在开源中国,看到了一个web版的javaMonitor。 虽然要在服务器上安装,但是这样的话,大家都能看见了。所以还是非常six的。 发现写了这个的博主也是非常...

miaojiangmin
26分钟前
3
0
Redis实践系列丨Codis数据迁移原理与优化

Codis介绍 Codis 是一种Redis集群的实现方案,与Redis社区的Redis cluster类似,基于slot的分片机制构建一个更大的Redis节点集群,对于连接到codis的Redis客户端来说, 除了部分不支持的命令外...

中间件小哥
26分钟前
3
0
HTTP常用状态码(14种)

类别 原因短语 1xx 信息型状态码 接收的请求正在处理 2xx 成功状态码 请求正常处理完毕 3xx 重定向状态码 需要进行附加操作以完成请求 4xx 客户端错误状态码 服务器无法处理请求 5xx 服务器错...

vio小黑
33分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部