插入排序

Author Avatar
Brian Lee 8月 02, 2018
  • 在其它设备中阅读本文章

《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/