插入排序分为:直接插入排序,折半插入排序,希尔排序。
这里我们主要分析最简单的:直接插入排序
自如其意,插入排序,就是每次读入一个元素的时候,在已经有序的序列中找到他应该插入的位置,然后插入保证当前序列还是有序,如此只能所有的元素都插入完毕。
int a[maxn],n;
void insertSort(){
for(int i=2;i<=n;i++){
int temp = a[i],j = i;
whlie(j>1 && temp < a[j-1]){
a[j] = a[j-1];
j--;
}
a[j] = temp;
}
}
稳定性:稳定