算法图解
插入第 i(范围0~length)个数,到有序队列的合适位置
假设数组长度 n , i(代表有序数组的长度) = 0
- 取第 i+1 个数,
插入到长度 i 有序数组的合适位置 - i+1
- 重复 1~2, 直到 i = n
实现
1
2
3
4
5
6
7
8
9
10
11
12
int n = array.length;
for (int i = 0; i < n - 1; i++) {
int waitToInsert = array[i + 1];
int pos = i + 1;
while (pos > 0 && waitToInsert < array[pos - 1]) {
// swap
array[pos] = array[pos - 1];
pos--;
}
array[pos] = waitToInsert;
}
时间复杂度
O(n) ~ O(n^2)
最好: 数组是有序的, 只需要遍历一遍
f(n) = n = O(n)
最差: 数组是混乱的
f(n) = n (n-1) / 2 = O(n^2)
空间复杂度
O(1) 没有使用到多余的空间
