CodePlayer

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

为了便于理解，我们同样以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原来的位置。

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

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

最后，教练让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的位置。

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

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

最后，我们仍然使用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