当前位置: 首页 > 技术随笔 > 插入排序入门详解

插入排序入门详解

在前面的文章中,我们介绍了冒泡排序选择排序,现在我们接着介绍插入排序

为了便于理解,我们同样以5名运动员的身高A(181)、B(169)、C(187)、D(172)、E(163)为例,并使用插入排序法完成对5名运动员身高的排序任务。

首先,教练先让排在左起第1位的A(181)站到更左侧,以便于和剩下的4名运动员形成明显的区分。教练想,以前的5名运动员之间的排列是无序的,现在我让左起第1位的运动员站出来,并把他看作一个已经按照要求排好序的队列,然后让右边剩下的4名运动员一个接一个依次插入到左侧的有序队列中,插入的位置按照排序的要求来插入。当所有运动员都插队完毕后,左侧的队列不就已经按照要求排序好了吗?

左侧的排列是一个有序排列左侧的排列是一个有序排列

现在,A(181)已经按照要求到左侧来了,于是,教练就继续按照他的设想,将左起第2位的B(169)插入到左侧的有序排列中。在插入之前,需要先确定插入的位置。所以需要将B与A的身高进行比较,由于B的身高比A小,所以A(181)需要向后退一个位置,将原来的位置让给B(169),B就插入在A原来的位置。

将B(169)插入到有序排列中将B(169)插入到有序排列中

接着,教练继续让左起第3位的C(187)插入到有序排列中,在插入之前,仍然需要确定插入的位置,于是将C(187)与前面(左起第2位)的A(181)比较身高,由于C(187)比较高,不需要让A(181)后退一位。由于左侧的有序排列是按照从小到大排列好的,C(187)比有序排列最右边、也就是有序排列中最高的A(181)还高,因此用不着再和有序排列左边的B(169)进行比较了。C(187)就直接排在A(181)的右侧。

将C(187)插入到有序排列中将C(187)插入到有序排列中

同理,教练继续让左起第4位的D(172)插入到有序排列中,在插入之前,先和有序排列最右侧、也是有序排列中最高的C(187)比较身高,由于D的身高比C小,所以C后退一位;接着D(172)和有序排列中的A(181)比较身高,由于D的身高比A小,所以A也后退一位;D(172)继续和有序排列的B(169)比较身高,由于B的身高比D小,所以B不用后退,D就插入到与B紧邻的右侧。

将D(172)插入到有序排列中将D(172)插入到有序排列中

最后,教练让E(163)插入到有序排列中。插入之前,E(163)先和C(187)比较,E较小C后退一位;E(163)继续和A(181)比较,E较小A后退一位;E(163)继续和D(172)比较,E较小D后退一位;E(163)继续和B(169)比较,E较小B后退——于是,E(163)就插入在原来B的位置。

将E(163)插入到有序排列中将E(163)插入到有序排列中

经过上面的排序步骤,现在就得到了我们所需要的排列。上面的排序过程实际上就是插入排序法的排序过程。

插入排序法,实际上就是将原来的排列分成两部分看,前面一部分看成有序排列(最初只有一个元素),后面一部分还是看作原来的无序排列,然后按照顺序依次让无序排列中的元素插队到有序排列中,插入的位置需要符合排序的要求,当无序排列中的人全部都插队到了有序排列中后,最后得到的就是我们所需要的排序结果。

最后,我们仍然使用Java代码来实现上述插入排序法的排序过程:

// =====使用插入排序法对表示5名运动员身高的数组heightArray进行从低到高的排序=====
		
// A(181)、B(169)、C(187)、D(172)、E(163)
int[] heightArray = { 181, 169, 187, 172, 163 };
int count = heightArray.length; // 参与排序的运动员总人数

for (int i = 1; i < count; i++) { // 外层循环控制插入身高的轮次数
	int insertHeight = heightArray[i]; // 当前需要插入的身高
	int comparedIndex = i - 1; // 用于与插入的身高进行比较的运动员索引
	// 内层循环控制本轮运动员的身高比较和位置交换工作
	while (comparedIndex >= 0 && heightArray[comparedIndex] > insertHeight) {
		// 如果用于比较的运动员比需要插队的运动员高,则让该运动员后退一个位置
		heightArray[comparedIndex + 1] = heightArray[comparedIndex];
		comparedIndex--; // 继续和前面一个比较
	}
	// 找到合适的位置后,插入到该位置
	heightArray[comparedIndex + 1] = insertHeight;
}// =====插入排序完成=====// 输出排序结果:
for (int height : heightArray) {
	System.out.println(height);
}

上述Java代码依然输出如下:

163
169
172
181
187
14 0
我们认为: 用户的主要目的,是为了获取有用的信息,而不是来点击广告的。因此本站将竭力做好内容,并将广告和内容进行分离,确保所有广告不会影响到用户的正常阅读体验。用户仅凭个人意愿和兴趣爱好点击广告。
我们坚信:只有给用户带来价值,用户才会给我们以回报。
CodePlayer技术交流群1CodePlayer技术交流群1

帮朋友打一个硬广告:

P2P网贷系统(Java版本) 新年低价大促销,多年P2P技术积累,系统功能完善(可按需定制,可支持第三方存管、银行存管),架构稳定灵活、性能优异、二次开发快速简单。 另可提供二次开发、安装部署、售后维护、安全培训等一条龙服务。

外行看热闹,内行看门道。可以自信地认为,在系统设计上,比市面上的晓风、迪蒙、方维、绿麻雀、国融信、金和盛等P2P系统要好。
深圳地区支持自带技术人员现场考察源代码、了解主要技术架构,货比三家,再决定是否购买。

也可推荐他人购买,一旦完全成交,推荐人可获得实际售价 10% 的返现。
有意向者,详情请 点击这里 联系,工作时间立即回复。