插入排序
插入排序的主要思想是取未排序区间的元素，在已排序区间找到合适的位置将它插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空。
案例
如图所示，要排序的数据是4，5，6，1，3，2，其中左侧为已排序区间，右侧是未排序区间
插入排序包含两种操作，一种是元素的比较，一种是元素的移动。
当我们需要将一个数据a插入到已排序区间时，需要拿a与已排序区间的元素依次比较大小，找到合适的插入位置。找到插入点之后，我们还需要将插入点之后的元素顺序往后移动一位，这样才能腾出位置给元素 插入。
对于不同的查找插入点方法（从头到尾、从尾到头），元素的比较次数是有区别的。但对于一个给定的初始序列，移动操作的次数总是固定的，就等于逆序度。
为什么说移动次数就等于逆序度呢？看了下面的图，你一看就明白了。满有序度是n*(n-1)/2=15，初始序列的有序度是5，所以逆序度是10。插入排序中，数据移动的个数总和也等于10=3+3+4。
代码
import java.util.Arrays; /** * @PackageName: cn.study.sufa.Day28 * @author: youjp * @create: 2022-05-15 21:56 * @description: TODo 插入排序 * @Version: 1.0 */ public class Solution { public void insertionSort(int[] a, int n) { if (n<0)return; for (int i = 0; i < n; i++) { int tmp =a[i]; int j= i-1; //查找插入的位置 for (;j>=0;--j){ if(a[j]>tmp){ a[j+1] =a[j];//数据移动 }else { break; } } a[j+1]= tmp;//插入数据 } } public static void main(String[] args) { int a[] ={24,21,3,5,99,88,90}; //输出排序结果 System.out.println("排序前"+ Arrays.toString(a)); new Solution().insertionSort(a,6); //输出排序结果 System.out.println("排序后"+Arrays.toString(a)); } }
总结
1.插入排序是原地排序算法吗？
从实现过程可以很明显地看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是O(1)，也就是说，这是一个原地排序算法。
2.插入排序是稳定的排序算法吗？
在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。
3.插入排序的时间复杂度是多少？
如果要排序的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下，最好是时间复杂度为O(n)。注意，这里是从尾到头遍历已经有序的数据。
如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据，所以最坏情况时间复杂度为O(n2)。
还记得我们在数组中插入一个数据的平均时间复杂度是多少吗？没错，是O(n)。所以，对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行n次插入操作，所以平均时间复杂度为O(n2)。
有兴趣的老爷，还可以关注我的公众号【一起收破烂】，回复【006】获取 最新java面试资料以及简历模型120套哦~
