折半插入排序

Posted on | Post modified: | In
Words count in article: 295 | Reading time ≈ 1

-折半插入算法介绍

折半插入排序

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

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！