文档章节

直接插入排序

JiaChang
 JiaChang
发布于 2016/08/13 09:25
字数 402
阅读 3
收藏 0
点赞 0
评论 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
海口
程序员

暂无文章

SpringBoot | 第十章:Swagger2的集成和使用

前言 前一章节介绍了mybatisPlus的集成和简单使用,本章节开始接着上一章节的用户表,进行Swagger2的集成。现在都奉行前后端分离开发和微服务大行其道,分微服务及前后端分离后,前后端开发的...

oKong
今天
4
0
Python 最小二乘法 拟合 二次曲线

Python 二次拟合 随机生成数据,并且加上噪声干扰 构造需要拟合的函数形式,使用最小二乘法进行拟合 输出拟合后的参数 将拟合后的函数与原始数据绘图后进行对比 import numpy as npimport...

阿豪boy
今天
1
0
云拿 无人便利店

附近(上海市-航南路)开了家无人便利店.特意进去体验了一下.下面把自己看到的跟大家分享下. 经得现场工作人员同意后拍了几张照片.从外面看是这样.店门口的指导里强调:不要一次扫码多个人进入....

周翔
昨天
1
0
Java设计模式学习之工厂模式

在Java(或者叫做面向对象语言)的世界中,工厂模式被广泛应用于项目中,也许你并没有听说过,不过也许你已经在使用了。 简单来说,工厂模式的出现源于增加程序序的可扩展性,降低耦合度。之...

路小磊
昨天
165
1
npm profile 新功能介绍

转载地址 npm profile 新功能介绍 npm新版本新推来一个功能,npm profile,这个可以更改自己简介信息的命令,以后可以不用去登录网站来修改自己的简介了 具体的这个功能的支持大概是在6这个版...

durban
昨天
1
0
Serial2Ethernet Bi-redirection

Serial Tool Serial Tool is a utility for developing serial communications, custom protocols or device testing. You can set up bytes to send accordingly to your protocol and save......

zungyiu
昨天
1
0
python里求解物理学上的双弹簧质能系统

物理的模型如下: 在这个系统里有两个物体,它们的质量分别是m1和m2,被两个弹簧连接在一起,伸缩系统为k1和k2,左端固定。假定没有外力时,两个弹簧的长度为L1和L2。 由于两物体有重力,那么...

wangxuwei
昨天
0
0
apolloxlua 介绍

##项目介绍 apolloxlua 目前支持javascript到lua的翻译。可以在openresty和luajit里使用。这个工具分为两种模式, 一种是web模式,可以通过网页使用。另外一种是tool模式, 通常作为大规模翻...

钟元OSS
昨天
2
0
Mybatis入门

简介: 定义:Mybatis是一个支持普通SQL查询、存储过程和高级映射的持久层框架。 途径:MyBatis通过XML文件或者注解的形式配置映射,实现数据库查询。 特性:动态SQL语句。 文件结构:Mybat...

霍淇滨
昨天
2
0
开发技术瓶颈期,如何突破

前言 读书、学习的那些事情,以前我也陆续叨叨了不少,但总觉得 “学习方法” 就是一个永远在路上的话题。个人的能力、经验积累与习惯方法不尽相同,而且一篇文章甚至一本书都很难将学习方法...

_小迷糊
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部