插入排序--详细动图讲解，时间复杂度分析！

插入排序

已同步微信公众号【乐享Coding】，欢迎关注！回复加群即可一起学习，领笔记资料！

基本思想：

将数组的第一个数认为是有序数组，后面的元素依次与有序数组的值从后往前进行比较，每次都需要比较到第一个元素，插入到有序数组的合适位置中，直到所有的元素均在有序数组中，就完成了排序。

举例：

本例中我们以arr数组[1, 9, -12, 0, 74]为例

步骤：

假设索引为0的第一个元素1是有序数组，先将索引为1的元素9与其进行比较，发现1<9,应该插在1的后面。

插入过程的代码思路：

• 定义一个临时变量temp存储待插入元素9，

• for循环遍历之前的元素，直至到第一个元素，循环中如果值小于前面元素，就将值赋给前面元素，否则就退出循环，

• 最后，退出循环将temp的值赋给当前位置，如果值小于相当于元素进行了前移。

int j, temp;
for (j = 1; j > 0 && arr[j-1] > temp; j--) //循环初始条件，终止条件，每轮的改变条件
    arr[j] = arr[j - 1];
arr[j] = temp; //退出循环后返还temp值

代码实现：

图解：

步骤二：

此时，[1,9]成为了有序数组，将第三个元素-12，与9和1依次进行比较，最终得到了有序数组[-12,1,9]

图解：

代码实现

int j, temp;
for (j = 2; j > 0 && arr[j-1] > temp; j--) //循环初始条件，终止条件，每轮的改变条件
    arr[j] = arr[j - 1];
arr[j] = temp; //退出循环后返还temp值

步骤三

重复以上步骤直到最后一个元素也插入完成。

动图详解：

最终代码实现：

  private static void insertSort(int[] arr) {
        int i, j, temp;
        for (i = 1; i < arr.length; i++) {
            temp = arr[i];
            for (j = i; j > 0 && arr[j-1] > temp; j--)
                arr[j] = arr[j - 1];
            arr[j] = temp;
        }
    }

总结

时间复杂度分析：

最坏情况下，n个元素需要比较1+2+3+…+n-1=(n+2)(n-1)/2次,移动的次数同样，因此时间复杂度很明显。

O(n^2)

空间复杂度分析：

没有用到任何的额外数据空间

O(1)

本文地址：https://blog.csdn.net/m0_46975599/article/details/112211889