插入排序的基本方法是：每步将一个待排序的元素，插入到前面已经排好序的一组元素的适当位置上去，直到元素全部插入为止。插入排序主要有直接插入排序、二分插入排序、希尔排序，本章主要介绍直接插入排序。

算法思想

将带排序元素插入到有序序列的对应位置

代码实现

public class Insertsort {
    public static void main(String[] args) {
        int[] array = new int[]{5,2,4,1,6,8,10,7,9,3};

        insertsort(array);

        for (int j : array) {
            System.out.println(j);
        }
    }

    public static void insertsort(int[] array) {
        for(int i=0;i<array.length;i++){
            int j = i;
            int temp = array[j];
            while(j-1 >= 0 && temp < array[j-1]){
                array[j] = array[j-1];
                j--;
            }
            array[j] = temp;
        }
    }
}

复杂度

时间复杂度

最好O(n)，最差O(n²)，平均O(n²)

空间复杂度

O(1)

稳定性

相同大小元素之间的相对位置并不会改变，稳定

总结

排序算法	时间复杂度	空间复杂度	稳定性
直接插入排序	最好O(n)，最差O(n²)，平均O(n²)	O(1)	稳定

插入排序之直接插入排序

Effy

算法思想

代码实现

复杂度

时间复杂度

空间复杂度

稳定性

总结

Other Articles

插入排序之二分插入排序

插入排序之希尔排序