一, 动图演示
二, 思路分析
例如从小到大排序:
1. 从第二位开始遍历,
2. 当前数 (第一趟是第二位数) 与前面的数依次比较, 如果前面的数大于当前数, 则将这个数放在当前数的位置上, 当前数的下标 - 1,
3. 重复以上步骤, 直到当前数不大于前面的某一个数为止, 这时, 将当前数, 放到这个位置,
1-3 步就是保证当前数的前面的数都是有序的, 内层循环的目的就是将当前数插入到前面的有序序列里
4. 重复以上 3 步, 直到遍历到最后一位数, 并将最后一位数插入到合适的位置, 插入排序结束.
根据思路分析, 每一趟的执行流程如下图所示:
三, 负杂度分析
1. 时间复杂度: 插入算法, 就是保证前面的序列是有序的, 只需要把当前数插入前面的某一个位置即可.
所以如果数组本来就是有序的, 则数组的最好情况下时间复杂度为 O(n)
如果数组恰好是倒 = 倒序, 比如原始数组是 5 4 3 2 1, 想要排成从小到大, 则每一趟前面的数都要往后移, 一共要执行 n-1 + n-2 + ... + 2 + 1 = n * (n-1) / 2 =0.5 * n2- 0.5 * n 次, 去掉低次幂及系数, 所以最坏情况下时间复杂度为 O(n2)
平均时间复杂度(n+n2 )/2, 所以平均时间复杂度为 O(n2)
2. 空间复杂度: 插入排序算法, 只需要两个变量暂存当前数, 以及下标, 与 n 的大小无关, 所以空间复杂度为: O(1)
四, Java 代码如下
- import java.util.Arrays;
- public class insertSort {
- public static void main(String[] args) {
- int[] n = new int[]{20,12,15,1,5,49,58,24,578,211,20,214,78,35,125,789,11};
- int temp = 0,j;
- for (int i = 1; i <n.length; i++) {
- temp = n[i];
- for (j = i; j>0; j--) {
- // 如果当前数前面的数大于当前数, 则把前面的数向后移一个位置
- if(n[j-1]>temp){
- n[j] = n[j-1];
- // 第一个数已经移到第二个数, 将当前数放到第一个位置, 这一趟结束
- if(j==1){
- n[j-1] = temp;
- break;
- }
- }else{// 如果不大于, 将当前数放到 j 的位置, 这一趟结束
- n[j] = temp;
- break;
- }
- }
- System.out.println(Arrays.toString(n));
- }
- System.out.println(Arrays.toString(n));
- }
- }
来源: https://www.cnblogs.com/l199616j/p/10594363.html