插入排序
《Algorithm》(Sedgewick)笔记:插入排序
原理
- 将每一个元素插入到其他已经有序的元素中的适当位置
- 为了给要插入的元素腾出空间,需要将其余所有元素在插入之前都向右移动一位
复杂度
时间复杂度
$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);
}
}
特点
- 插入排序所需要的时间取决于输入中元素的初始顺序
- 插入排序对于部分有序数组十分高效,也很适合小规模数组
源码
本博客采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!
本文链接:http://brianleelxt.top/2018/08/02/InsertionSort/