前言
真的，看到挺多博客的插入排序，思路大多都是对的，但是在代码实现上不严谨，甚至还有的跟冒泡排序搞混了，还是有必要分析波插入排序，希望能帮助到大家。
一.插入排序原理
插入排序原理是：逐步构建有序的序列，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
二.图解
三.实现思路
插入排序分为3种情况：
1.当前节点<前面的A节点时，A节点后移一位，接着向前继续比较。
2.当前节点>前面的A节点时，当前节点插入到A节点的后一个位置，此时不需要再继续比较了，因为A节点及之前的元素已经是有序的了
3.当前节点<前面的A节点时，并且A节点的位置是0时，需要连续两步操作：A节点往后移一位，当前节点插入到数组下标为0的位置。
如果这个思路看不懂没关系，请看代码，有更详细的解释。
四.代码实现
语言采用Java来实现，如果看不懂java代码关系也不大，基本每行都有解释
/** * 实现思路： * 插入排序需要考虑3种情况： * 1.当前节点<前面的A节点时，A节点后移一位，接着继续比较 * 2.当前节点>前面的A节点时，当前节点插入到A节点的后一个位置，此时不需要再继续比较了，因为A节点及之前的元素已经是有序的了 * 3.当前节点<前面的A节点时，并且A节点的位置是0时，需要连续两步操作：A节点往后移一位，当前节点插入到数组下标为0的位置 * */ public static int[] InsertionSortByFor(int[] arr) { /** * 最多遍历arr.length-1轮，i的值表示每轮从哪个位置开始向前比较； * 比如arr[1]，那么arr[1]就和arr[0]进行比较 * arr[2]，从arr[2]向前扫描比较 * arr[3],从arr[3]向前扫描比较 * 依次类推 */ for(int i=1;i<arr.length;i++) { int temp = arr[i]; //temp是保存着每轮当前节点的值，保存的目的是用于与前面的值做比较 for(int j=i-1;j>=0;j--) { //j的值记录的是当前节点的前面元素的下标位置; //只要满足j>=0，元素的比较才能进行，若j<0就会超出数组下标的范围 //j--才能比较前面的元素 if(temp<=arr[j]) { //当前节点<前面的A元素，那么A元素往后移 arr[j+1] = arr[j]; if(j==0) { //这里属于特殊情况，当temp<=arr[j]以及j==0时，需要连续两步操作：1.A元素往后移 2.当前节点插入到arr[0]的位置 arr[j] = temp; } }else{ //当前节点>前面的A元素,那当前节点插入到A元素的后面，即j+1的位置 arr[j+1] = temp; break; //break是到这一步就不需要再往前比较了，因为A元素及之前的元素已经是有序了 } } } return arr; }
main方法测试：
public static void main(String[] args) { //创建一个无序数组 int[] arr = new int[] {3,6,1,87,90,34,34,25}; //调用插入排序方法，返回一个排序后的数组 int[] sortedArr = InsertionSortByFor(arr); //遍历数组 for(int i=0;i<sortedArr.length;i++) { System.out.print(sortedArr[i]+" "); } }
测试结果：
其实说得挺详细的了，基本都有注释，如果有不懂欢迎大家下面留言，上面的代码其实还有优化的空间，只不过临时写的，一些细节可能处理不到位请见谅
可以的话给个推荐，让我知道你来过！