插入排序就是将待插入元素一个个插入初始已有序部分中的过程，而插入位置的选择遵循了使插入后仍保持有序的原则，具体做法一般是从后往前枚举已有序部分来确定插入位置。 具体实现：
int A
[maxn
],n
;
void insertSort(){
for(int i
=2;i
<n
;i
++){
int j
=i
,temp
=A
[i
];
while(j
>1&&temp
<A
[j
-1]){
A
[j
]=A
[j
-1];
j
--;
}
A
[j
]=temp
;
}
}
