在前面的文章中,我们介绍了冒泡排序和选择排序,现在我们接着介绍插入排序。
为了便于理解,我们同样以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
未经允许请勿转载:程序喵 » Java插入排序入门详解