1.将最小的元素放在最前.将最小元素作为关键字.
2.索引的左则是以排好序的,但不是处于最终位置.当碰到更小的数据向右移动腾出空间,插入较小的数据.
3.索引加一并重复上叙步骤.
3.当索引移到最右则时,则数组拍好序.
和选择排序不同的是,插入排序的运行时间和数据的原始排列顺序密切相关.
如果数据量比较大,而且已经排好序或几乎排好序,插入排序比选则排序好.
下面给出C代码的实现.
//a:数组
//l:数组的长度
void insertion(int a[],int l)
{
int i,j;// 索引
int temp;// 用于交换
int v;
// 将最小的元素放在最前.
for(i = l-1; i>0; –i)
{
// 进行小于比较
if(a[i-1] < a[i])
{// 交换
temp = a[i-1];
a[i-1] = a[i];
a[i] = temp;
}
}
for(i=2; i < l; ++i)
{
j = i;
v = a[i];
// 小于比较
while(v < a[j-1])
{// 向右移
a[j] = a[j-1];
j–;
a[j] = v;
}
}
}