《Algorithm》（Sedgewick）笔记：插入排序

原理

1. 将每一个元素插入到其他已经有序的元素中的适当位置
2. 为了给要插入的元素腾出空间，需要将其余所有元素在插入之前都向右移动一位

复杂度

时间复杂度

$O(n^2)$

空间复杂度

$O(1)$

图示

代码

public static void sort(Comparable[] a) {
    int N = a.length;
    for (int i = 1; i < N; i++) {
        for (int j = i; j > 0 && less(a[j], a[j - 1]); j--)
            exch(a, j , j - 1);
    }
}

特点

• 插入排序所需要的时间取决于输入中元素的初始顺序
• 插入排序对于部分有序数组十分高效，也很适合小规模数组

源码

https://github.com/XutongLi/Algorithm-Learn/blob/master/src/S2_Sorting/S2_1_3_Insertion_Sort/Insertion.java

本博客采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处！
本文链接：http://brianleelxt.top/2018/08/02/InsertionSort/