折半插入排序

-折半插入算法介绍

折半插入排序

如果线性表是有序的,进行查找可以用折半查找来实现。在确定出待插入位置后,就可以统一的向后移动元素了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void InsertSort(ElemType A[],int n){
int i,j,low,high,mid;
for(i=2;i<=n;i++){ //依次将A[2]~A[n]插入到前面已排好序的序列中
A[0]=A[i]; //将A[i]暂存到A[0]
low=1;
high=i-1; //设置查找范围
while(low<=high){
mid=(low+high)/2; //去中间点
if(A.[mid].key>A[0].key)
high=mid-1; //查询左子表
else
low=mid+1; //查询右子表
}
for(j=i-1;j>=high+1;--j)
A[j+1]=A[j]; //统一后移元素,空出插入位置
A[high+1]=A[0]; //插入操作
}
}

从上述算法中,不难看出折半插入排序仅仅是减少了比较元素的次数,约为O(nlog2n),该比较次数与待排序表的初始状态无关,仅取决于表中元素个数n;而元素的移动次数没有改变,它取决于待排序表的初始状态。因此,折半插入排序的时间复杂度仍为O(n2)


Thanks for your reward!