Java排序算法——插入排序（Insertion Sort）

article/2025/10/24 6:43:07

之前总结了交换排序的冒泡排序与选择排序的简单选择排序，这次我们来看看插入排序的简单插入排序~

往期传送门：

冒泡排序：

Java排序算法——冒泡排序（Bubble Sort）https://blog.csdn.net/babbfqb93/article/details/123005968简单选择排序：

Java排序算法——选择排序（Selection Sort）https://blog.csdn.net/babbfqb93/article/details/123040023插入排序（Insertion Sort）一般也被称为直接插入排序或者简单插入排序，之所以这样，是因为我们一般把排序算法分为比较类排序与非比较类排序，而比较类排序又可以分为交换排序、插入排序、选择排序与并归排序。整体如下图：

我们已经讲过了冒泡排序与选择排序（简单选择排序），可以明确感觉的出来，冒泡排序——交换排序，可以看出来是每个比较，之后进行交换。简单选择排序，我们先“选择”需要交换的元素，然后交换，再进行交换这种方式进行排序。现在我们要总结的简单插入排序，则和之前又有所不同。

插入排序，故名思意，是一种“插入”的排序。我们视同原始数据为“无序数组”，将“无序数组”的元素，逐个将元素。插入到“有序数组”中，这一句话总结，可能不太能好理解，所以我们先看一下整体的实现。先把整体的图给大家看一下效果：（最后一栏出现“插入”字符串，说明进行了插入操作）。

我们先看一下第一行的数据，用它作为例子

第一步（分析）：

原始数组，我们默认数组的第一个元素视同一个长度为1的“有序数组”，毕竟他就一个元素，怎么看都是有序的。接下来我们把剩余的数组视同为无序的。

第二步（获取需要比较的元素）：

“红色标记”为我们要比较的元素，我们获取第一个“无序数组”的元素“20”，它是我们本次循环需要被比较的数字。

第三步（获取被比较的元素）：

“黄色标记”为我们被比较的元素，它的取数逻辑是从“有序数组”的最后一个元素开始，如本次比较，“40”就是我们被比较的数字。

第四步（比较）：

如果“红色”比“黄色”大，则记录下当前“黄色”的下标位置，如果结果是小，则继续和“黄色“的上一位比较，直到找到比“红色”小的“黄色”来记录下标或者遍历完整个“有序数组”。

第五步（插入）：

将“红色”插入到记录下的坐标位置，如果没有记录的位置，则视同位置为数组的起点“0”下标。

以上5步可以理解为插入排序的一个内层循环，我们可以用代码将其实现，实现代码如下：

生成随机数方法和之前的方法都是一致的：

//初始换一个长度为参数的随机数组，数组元素为0（含）到50（不含）的随机数
public static int[] initArray(int length){Random r = new Random();//申明并实例化一个Random对象int[] iArray = new int[length];//申明并实例化一个int数组用于测试排序for (int i = 0; i < iArray.length; i++) {//通过Random随机生成一个0（含）到50（不含）的数并插入对应位置iArray[i] = r.nextInt(50);}return iArray;
}

插入方法，插入方法和之前的交换方法不相同，我们的插入不是简单的交换，而是将之前的数字向后移动一位，直到到需要插入的位置，将数值插入进去：

//将下标为i的元素插入到下标为j的元素
public static void swap(int[] iArray,int i,int j){//先将j下标位置存储int temp = iArray[i];//当i>j的时候需要循环，直到j与i坐标相当，每次将j之前一个数向后移动一位，j--for(;i>j;i--){iArray[i]=iArray[i-1];}//最后将i下标设置成被插入数的值iArray[j]=temp;
}

简单插入排序第一层循环逻辑：

public static void insertionSort(int[] iArrays){//默认和0进行交换int index = 0;//被比较的数（“红色”）int temp = iArrays[0 + 1];//遍历之前的“有序数组”，从总循环次数+1开始遍历for (int j = 0+1; j >0; j--) {//如果需比较的数字大于之前的某一个元素，记录元素的下标用于插入if(temp >iArrays[j-1]){index = j;}}//插入交换swap(iArrays,0+1,index);}

这就是第一次的循环，接下来我们需要的就是让所有的数都会被遍历到，并且按照之前的5步走，那么就是将循环次数再次嵌套一层循环，循环的起点是从第0个下标位置开始，终点为数组的最后一个数字之前一位（内层循环会将该次数+1（int j = i+1）所以条件的终点应该是数组长度-1），加上之后讲之前的0改成外层循环变量i就实现了。

public static void insertionSort(int[] iArrays){//循环整体数据for(int i =0;i<iArrays.length-1;i++) {//默认和0进行交换int index = 0;//被比较的数（“红色”）int temp = iArrays[i + 1];//遍历之前的“有序数组”，从总循环次数+1开始遍历for (int j = i + 1; j > 0; j--) {//如果需比较的数字大于之前的某一个元素，记录元素的下标用于插入if ( temp > iArrays[j - 1]) {index = j;//因为之前为有序的所以记录坐标就可以break了break;}}//插入交换swap(iArrays, i + 1, index);}
}

我们写个测试入口测试一下：

public static void main(String[] args) {//初始化数组int[] iArray = initArray(7);//输出排序前结果System.out.println("------排序之前------");System.out.println(Arrays.toString(iArray));System.out.println("-------------------");//排序...System.out.println("------正在排序------");insertionSort(iArray);System.out.println("-------------------");//输出排序后结果System.out.println("------排序之后------");System.out.println(Arrays.toString(iArray));System.out.println("-------------------");
}

实现结果：