文档章节

直接插入排序

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
海口
程序员
私信 提问

暂无文章

Pages Manager——可本地管理Pages服务内容,一键生成漂亮的文档界面。

Pages Manager Git地址 可本地管理Pages服务内容,一键生成漂亮的文档界面。在线预览 简单、轻便,无需安装数据库。 框架:spring-boot 数据库:sqlite 原理 本地维护一组markdown文档 将mar...

tanghc
10分钟前
0
0
基础目标检测算法介绍:CNN、RCNN、Fast RCNN和Faster RCNN

每次丢了东西,我们都希望有一种方法能快速定位出失物。现在,目标检测算法或许能做到。目标检测的用途遍布多个行业,从安防监控,到智慧城市中的实时交通监测。简单来说,这些技术背后都是强...

AI女神
10分钟前
0
0
哪有什么互联网寒冬?只是你穿的少而已!

声明:本文由终端研发部原创发布,未经允许,不得转载 前言 最近一段时间,大家都在说一些大公司纷纷裁员, 优化公司内部的组织架构。面对如此的寒冬变化,很多人在迷茫,在焦虑,在担忧自己...

终端研发部
15分钟前
0
0
nginx: [error] open() "/var/run/nginx.pid" failed (2: No such file or directory)

Nginx 启动时报错:nginx: [error] open() "/var/run/nginx.pid" failed (2: No such file or directory) 原因:系统重启 /var/run/ 目录下文件会清空。 方法一: # sudo nginx -c /etc/ngi......

驛路梨花醉美
18分钟前
1
0
TiDB 源码阅读系列文章(二十四)TiDB Binlog 源码解析

作者:姚维 TiDB Binlog Overview 这篇文章不是讲 TiDB Binlog 组件的源码,而是讲 TiDB 在执行 DML/DDL 语句过程中,如何将 Binlog 数据 发送给 TiDB Binlog 集群的 Pump 组件。目前 TiDB 在...

TiDB
31分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部