基础算法-插入排序算法
基础算法-插入排序算法
插入排序算法，大体思想是：将数组中未排序的元素，逐个与前面已经完成排序的元素进行比较大小，选择合适的位置插入进去，依此想法，不断重复，直至完成最后一个元素的排序。
通过一个示例，再进行更简单的理解。比如，我们现在有一个int[]类型的数组，主要元素有{23,84,5,70,39,14,43}，是无序的。按照上面描述的思想，怎么利用插入排序算法排序呢？
对于第一个元素23，它前面是没有元素的，我们可以理解为它已经排好一轮，当前就排在第一个位置，不需要我们移动。对于后面的84、5、70、39、14、43，则需要我们比较了。在比较时，我们可以将前面已经排好顺序的元素，看作一个“子数组”。
将84与23比较，发现84比23大，应该排在23后面，我们发现不需要我们移动，此时，23与84已经按照从小到大的顺序排好了。而前面说的“子数组”中的元素也由23，增加到了23、84.
下一个是5，将5与“子数组”中的84比较，发现5比84小，所以将5插入到“子数组”中，得到的“子数组”结果是23、5、84；接着比较发现，5又比23小，所以5要插入到23之前，那么得到的“子数组”结果是{5、23、84}。至此，对于5与之前完成排序的23、84之间的比较和插入位置，就完成。
轮到70，类似上面的5一样，将70与“子数组”中的84比较，70比84小，所以70要插入到84的前面，得到“子数组”{5、23、70、84}，再比一下，发现70比23大，所以不用动，完成这一轮排序。
后面的元素，按照上面的做法，依次逐个与前面已经完成排序的元素进行比较，并找到合适的位置完成插入操作，直到最后一个元素结束，从而完成整个插入排序。
看下具体实现代码：
package com.daily;
import java.util.Arrays;
/**
* @description 插入排序算法
* 插入排序算法，将未排序的元素，逐个与之前已经完成排序的元素进行比较大小，选择合适的位置插入进去，不断重复，直至完成最后一个元素的排序
* @author yuhuofei2021
* @date 2021年6月24日
*/
public class InsertionSort {
public static void main(String[] args) {
int[] array = new int[] {23,84,5,70,39,14,43};
insertionSort(array);
}
/**
* @description 插入排序算法具体实现
* @author yuhuofei2021
* @date 2021年6月24日
* @param arr
*/
public static void insertionSort(int[] arr) {
//定义两个变量j和temp，j用来标记数组元素下标，temp用来暂时保存当前这第i轮比较中arr[i]这个元素的值
int j,temp;
for (int i = 1; i < arr.length; i++) {
temp = arr[i];
for (j = i; j > 0; j--) {
/*将arr[i]赋值给temp后 ，拿到了一个定值temp；
*将arr[i]这个元素之前的所有数组元素形成一个子数组，以arr[j]表示这个子数组的元素，与定值temp进行比较；
*如果有元素比temp大，则将该元素向后移动一个位置，并且完成j自减1，即j--或者是j=j-1
*最后把本轮的定值temp，赋值给j完成自减后的arr[j]
*/
if (temp < arr[j-1]) {
arr[j] = arr[j-1];
}else {
break;
}
}
arr[j] = temp;
//打印每一轮的排序结果
System.out.println("第"+i+"轮排序结果："+Arrays.toString(arr));
}
//打印最终排序的结果
System.out.println("最终排序结果：" + Arrays.toString(arr));
}
}
每一轮比较的打印输出结果：
第1轮排序结果：[23, 84, 5, 70, 39, 14, 43]
第2轮排序结果：[5, 23, 84, 70, 39, 14, 43]
第3轮排序结果：[5, 23, 70, 84, 39, 14, 43]
第4轮排序结果：[5, 23, 39, 70, 84, 14, 43]
第5轮排序结果：[5, 14, 23, 39, 70, 84, 43]
第6轮排序结果：[5, 14, 23, 39, 43, 70, 84]
最终排序结果：[5, 14, 23, 39, 43, 70, 84]