Intro

插入排序算法是基础排序算法的一种,相比选择排序算法具有不错的性能提升。

时间复杂度

遍历一趟序列的时间假设为\( O(N) \),总共需要遍历的次数为\( N-1 \)次,那么此算法的时间复杂度为\( O(N^2) \)

代码实现

插入排序算法的实现比较简单,我们无需关注暂未被排序的子序列,永远关注的是目前index为止的位置元素与其左边元素的大小比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package net.sunzhenyu.miscellaneous.dsa.sort;

public class InsertionSort implements Sort{

@Override
public void sort(Comparable[] c) {
int steps = c.length;
for (int i = 0; i < steps; i++) {
for (int j = i; j > 0 ; j--) {
if (less(c[j], c[j - 1])) {
exchange(c, j, j - 1);
}
}
}
}

private void exchange(Comparable[] c, int i, int j) {
Comparable oldValue = c[i];
c[i] = c[j];
c[j] = oldValue;
}
}