插入排序-直接插入排序

算法简介

直接插入排序应该是插入排序中最简单的一种，前几篇博文已经写了冒泡排序（交换排序中最简单的一种），简单选择排序（选择排序中最简单的一种），今天我们来看看直接插入排序的思路和写法

直接插入排序时间复杂度 O(n^2)，空间复杂度 O(1)，一般来说它是稳定的排序

Java 实现

思路

思路很明确，就是我通过两轮循环，最外层循环是用来遍历每一个要插入的数，内层循环是为了确定这个数是要插入到序列什么位置。假设头部是一段有序的序列，我从下标 1 的元素开始，不断与头部已经有序的序列比较，从而插入其中，然后再是下标为 2 的元素再插入……最后是末尾元素插入前面有序的序列，最终达到有序效果

代码实现

// 直接插入排序（从小到大）
public int[] directInsertionSort(int[] arr) {
    for (int i = 1; i <= arr.length - 1; i++) {
        int temp = arr[i];
        for (int j = i - 1; j >= 0; j--)
            if (temp < arr[j])
                arr[j+1] = arr[j];
        a[j+1] = temp;
    }
    return arr;
}

时间复杂度

时间复杂度 O(n^2)

空间复杂度

空间复杂度 O(1)

算法稳定性

一般来说是稳定的排序算法