思路
- 前2个元素排序：把第2个元素放到“前1个元素组成的有序数组”中。
- 前3个元素排序：把第3个元素放到“前2个元素组成的有序数组”中。
- 前4个元素排序：把第4个元素放到“前3个元素组成的有序数组”中。
- ……
- 前n个元素排序：……
平均时间复杂度：O(n2)
实现
void insert_sort(const int* a, int length){
for(int i = 1; i < length; i++){
int k = a[i];
for(int j = i-1; j >= 0; j--){
if(a[j] > a[i]){
a[j+1] = a[j];
}else {
break;
}
}
a[j] = k;
}
}
关键点注释
与冒泡相似。区别只在内遍历的范围：是从i + 1到0.
