|
插入排序的基本思想是，经过i-1遍处理后,a1,a2,..,ai-1己排好序。第i遍处理仅将ai插入a1,a2,..,ai-1的适当位置，使得a1,a2,..,ai又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较ai和ai-1，如果ai-1 ≤ ai，则a1,a2,..,ai已排好序，第i遍处理就结束了；否则交换ai与ai-1的位置，继续比较ai-1和ai-2，直到找到某一个位置j(1≤j≤i-1)，使得aj ≤ aj+1时为止。图1演示了对4个元素进行插入排序的过程。
图1 对4个元素进行插入排序
在下面的插入排序算法中，为了写程序方便我们可以引入一个哨兵元素a0，它小于a1,a2,..,an中任一记录。所以，我们设元素的类型TElement中有一个常量-∞，它比可能出现的任何记录都小。如果常量-∞不好事先确定，就必须在决定ai是否向前移动之前检查当前位置是否为1，若当前位置已经为1时就应结束第i遍的处理。另一个办法是在第i遍处理开始时，就将ai放入a0中，这样也可以保证在适当的时候结束第i遍处理。
例：
|
初始序列：
|
8
|
3
|
2
|
5
|
9
|
1
|
6
|
|
i=2
|
3
|
8
|
2
|
5
|
9
|
1
|
6
|
|
i=3
|
2
|
3
|
8
|
5
|
9
|
1
|
6
|
|
i=4
|
2
|
3
|
5
|
8
|
9
|
1
|
6
|
|
i=5
|
1
|
2
|
3
|
5
|
8
|
9
|
6
|
|
i=6
|
1
|
2
|
3
|
5
|
8
|
9
|
6
|
|
i=7
|
1
|
2
|
3
|
5
|
6
|
8
|
9
|
程序如下：
直接插入排序:
void docr(float *in,int count)
{
int i,j,x;
float temp;
for(i=1;i<count;i++)
{
for(x=0;x<i;x++)
{
if((*(in+i))<=(*(in+x)))
break;
}
temp=*(in+i);
for(j=i;j>x;j--)
{
*(in+j)=*(in+j-1);
}
*(in+x)=temp;
}
}
最小比较次数：n 最大比较次数：n*n/2
最小移动次数：2n 最大移动次数：n*n/2
二分法插入排序:(比较部分用二分法)常用算法
void docr(float *in,int count)
{
int i,j,x;
int l,r,m;
float temp;
for(i=1;i<count;i++)
{
l=0;
r=i-1;
temp=*(in+i);
while(l<=r)
{
m=(int)((l+r)/2);
if(temp<=(*(in+m)))
{
r=m-1;
}
else
{
l=m+1;
}
}
for(j=i;j>l;j--)
{
*(in+j)=*(in+j-1);
}
*(in+l)=temp;
}
}
移动次数: n*log2(n)
最小移动次数：2n 最大移动次数：n*n/2
|
