图解排序算法(三)之折半插入排序

折半插入排序利用二分法的思想，在一个有序的序列中，找到新元素在该序列中的位置，然后插入。如图1所示，共有n个元素，前i个元素已经是有序序列，现在要将第i个元素插入其中。折半插入排序需要做两步工作：找到待插入元素的位置、插入。

 

图1 插入排序示意图

 

首先要定义两个指针(不是语法里面的指针，是下标的意思)low和high用于寻找a[i]的插入位置，low指向a[0]，high指向a[i-1]，中点mid=(low+high)/2，

图2 “折半”示意图

 

如图2所示二分法的思想是，比较a[i]与a[mid]的大小，若a[i]>a[mid]，说明a[i]的位置应该在mid~high之间，将区间[low,high]缩短为[mid+1,high]，令指针low=mid+1；若a[i]<=a[mid]，说明a[i]的位置应该在low~mid之间，将区间压缩为[low,mid-1]，令指针high=mid-1。每次折半之后，a[i]的位置应该在[low,high]之间。

如此循环，low与high渐渐靠近，直到low>high跳出循环，a[i]的位置找到，low即为a[i]应该放置的位置。

找到a[i]的位置之后进行插入，先将a[low]~a[i-1]这些元素向后平移一个元素的位置，然后将a[i]放到low位置。

 

代码实现

#include <iostream>
using namespace std;

void BinSort(int *a,int n) //对int数组进行从小到大的排序 
{
	for(int i=1;i<n;i++) //开始 以a[0]作为有序序列，从a[1]开始找到当前元素a[i]应该放置的位置 
	{
		int low=0,high = i-1,mid;//每次寻找a[i]的位置，都要更新这些数据 
		while(low<=high) //二分思想循环寻找a[i]的位置 
		{
			mid = (low+high) / 2;  
			if(a[i]<=a[mid])
				high = mid - 1;  //high指针减小 
			else
				low = mid + 1;   //low指针增加 
		}  //循环结束，low就是a[i]应该放置的位置 
		
		int temp = a[i];  
		for(int j=i;j>low;j--)  //将元素向后平移
			a[j] = a[j-1];  
		a[low] = temp;   //将元素temp = a[i] 放置到low位置 
	}
}

int main()  //举例说明
{
	int n = 10;
	int a[10] = {5,8,9,4,7,5,6,3,1,11}; 
	BinSort(a,n);
	for(int i=0;i<n;i++)
		cout << a[i] << " ";
	cout << endl;
	
	return 0;
}

总结：
折半插入排序算法相比较于直接插入排序算法，只是减少了关键字间的比较次数，而记录的移动次数没有进行优化，所以该算法的时间复杂度仍是 O(n2)。