您的浏览器过于古老 & 陈旧。为了更好的访问体验, 请 升级你的浏览器
Ready 发布于2013年08月30日 12:48 最近更新于 2019年05月27日 19:43

原创 插入排序入门详解

1981 次浏览 读完需要≈ 8 分钟 排序算法

内容目录

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

为了便于理解,我们同样以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)插入到有序排列中

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

将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)插入到有序排列中

最后,教练让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)插入到有序排列中

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

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

最后,我们仍然使用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
  • CodePlayer技术交流群1
  • CodePlayer技术交流群2

0 条评论

撰写评论