(兔C残篇)直接插入排序的实现与讲解

本文主要是介绍(兔C残篇)直接插入排序的实现与讲解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.概述

直接插入排序方式是一种最简单的排序方法：他的基本操作是将一个记录插入到一个长度为m的有序列表中，使之仍保持有序。

例如：有这样一个数组 int arr[] = {50,10,20,30,60,70,40,80,90};
其中的元素为：[50,10,20,30,60,70,40,80,90]

那直接插入的排序方式就会把第一个元素看成是一个有序的数组
[50]
然后其余的元素会通过循环比较后插入到[50]这个数组当中，
[50]这个数组是个有序的数组，因为其中只有一个元素啊。

2. code 编写

public class ReturnNumber{public static void main(String[] args){//定义数组int arr[] ={50,10,20,30,60,70,40,80,90};//定义循环，控制比较的轮数for(int i =1; i <arr.length; i++){//起始值从1开始，直接插入排序便是从第一个元素开始循环。//设置内层循环，对 条件满足情况下的元素进行控制//注意这里需要定义一个变量，将其当做内层循环的下标int index = i;while(arr[index] < arr[i]){int temp = arr[index];arr[index] = arr[i];arr[i] = temp;index--;/* 循环环境下，外层在控制数组的轮数，内层控制元素当条件吻合，交换元素位置后的下一次循环需要移动到前一个位置继续进行比较所以--。简而言之，直接插入进去的元素，插队了，--动作就是移动到插队进去的下标处下一次循环的开始，从插队者开始进行比较。*/}}System.out.println("插接插入排序后的元素内容为："+Arrays.toString(arr));}
}

3. 数组下标越界异常

此时代码执行之后一定是有问题的！！
Java.lang.ArrayIndexOutOfBoundsException
因为代码都是我为了检验自己是否掌握，直接在文档编辑过程中，CSDN中手写的。
我开始以为写好了，但是粘贴到idea里果然出问题了。

4. 问题的分析与排查

分析一下问题：
首先要明确两层循环的意义：
外层循环控制的是轮数，内层循环控制的当前轮数的元素。
在冒泡排序，和选择排序中，都是嵌套for，但是直接插入排序的话，它的特点是把第一个元素看成是一个有序数组，后续的内容 当做是一个集合，经过比较插入到这个有序数组中，从而得到一个新的排序好的有序数组。

然后理清楚内层循环的设置，毕竟外层循环是对轮数的控制，大脑不短路情况下不会出现太大问题
又由于内层的循环次数不确定，选用了while循环，此时需要更改的地方有两处：

1. while 循环中的条件，应该是当前轮数的前两个元素进行比较，而不是上述demo中的糊涂写法
2. 第二点就是 index-- 的减减操作，如果当index的值已经为0了，那继续index–操作，会不会减到负数？对吧，所以会出现Java.lang.ArrayIndexOutOfBoundsException

5. code的二次改造

下面进行二手房翻新工作：

public class ReturnNumber{public static void main(String[] args){//定义数组int arr[] ={50,10,20,30,60,70,40,80,90};//定义循环，控制比较的轮数for(int i =1; i <arr.length; i++){//起始值从1开始，直接插入排序便是从第一个元素开始循环。//设置内层循环，对 条件满足情况下的元素进行控制//注意这里需要定义一个变量，将其当做内层循环的下标int index = i;while(index >0 &&arr[index] < arr[index-1]){int temp = arr[index];arr[index] = arr[index-1];arr[index-1] = temp;index--;/* 循环环境下，外层在控制数组的轮数，内层控制元素当条件吻合，交换元素位置后的下一次循环需要移动到前一个位置继续进行比较所以--。简而言之，直接插入进去的元素，插队了，--动作就是移动到插队进去的下标处下一次循环的开始，从插队者开始进行比较。*/}}System.out.println("插接插入排序后的元素内容为："+Arrays.toString(arr));}
}

6. 改造效果图

来看一下二手房翻新后的效果：

7. 第二种写法： 两层for嵌套

public class ReturnNumber{public static void main(String[] args){//定义数组int arr[] ={50,10,20,30,60,70,40,80,90};//定义循环，控制比较的轮数for(int i =1; i <arr.length; i++){//其实整个改造过程中，没有任何的变化，只要掌握好控制元素的条件设置// 1.内层循环的起始值下标设置// 2.循环轮数中，控制元素的交换条件// 3.结束一轮之后，下标的指向设置for(int j = i; j > 0; j--){if (arr[j] < arr[j-1]) {int temp = arr[j];arr[j] = arr[j - 1];arr[j - 1] = temp;}}}System.out.println("插接插入排序后的元素内容为："+Arrays.toString(arr));}
}

8. 冗余代码抽取

最后我们在把冗余的代码抽取成方法

public class ReturnNumber{public static void main(String[] args){//定义数组int arr[] ={50,10,20,30,60,70,40,80,90};//定义循环，控制比较的轮数for(int i =1; i <arr.length; i++){//其实整个改造过程中，没有任何的变化，只要掌握好控制元素的条件设置// 1.内层循环的起始值下标设置// 2.循环轮数中，控制元素的交换条件// 3.结束一轮之后，下标的指向设置for(int j = i; j > 0; j--){if (arr[j] < arr[j-1]) {ifNumber(arr, j, j - 1);}}}System.out.println("插接插入排序后的元素内容为："+Arrays.toString(arr));}public static void ifNumber(int[] arr,int i, int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}

OKK，直接插入排序打完收工。

这篇关于(兔C残篇)直接插入排序的实现与讲解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---