排序之二分插入排序

作为一个稳定的排序算法， 插入排序很重要，大多数程序员都可以很轻松的写出插入排序！

先看一下插入排序的代码：

void sort_insert(int a[],int n)
{
	int i,j;
	i=1;
	while(i<n)
	{
		int x = a[i];
		j=i-1;
		while(j>=0 && a[j]>x)
		{
			a[j+1]=a[j];
			j--;
		}
		a[j+1] = x;
		i++;
	}
}

如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。

最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。

最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1）次。

平均来说插入排序算法的时间复杂度为O(n^2）。因而，插入排序不适合对于数据量比较大的排序应用。

但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。

由于插入排序每次插入时都在一个已经已排序的序列中进行插入，所以利用分治的思想！我们当然也可以利用二分法进行插入。

先跟序列最中间的那个元素比较，如果比最中间的这个元素小，则插入位置在它的左边，否则在它的右边。

以当前最中间位置为分割点，如果在左边，则当前最中间位置是待搜索子序列的终点，如果在右边，右边邻接的元素将是待搜索子序列的起点。

按照这种原则，继续寻找下一个中间位置，并继续这种过程，直到找到合适的插入位置为止。

最坏的情况下二分插入排序的时间复杂度依然是O(n^2),

如果待排序的序列已经有序，排序时间复杂度为O(nlogn)。

由此可见，二分插入排序的算法已经对插入排序做了一定的优化！

好了话不多说，上代码：

void sort_binary_insert(int a[],int n)
{
	int i,j;
	i=1;
	while(i<n)
	{	int x=a[i];
		int head = 0;
		int tail = i-1;
		while(head<=tail)
		{
			int mid = (head+tail)/2;
			if(x<a[mid])
				tail=mid-1;
			else
				head=mid+1;
		}
		for(j=i-1;j>=head;j--)
		{
			a[j+1]=a[j];
		}
		a[head]=x;
		i++;
	}
}

祝大家春节快乐！

排序之二分插入排序

原文：http://blog.csdn.net/tiny39st/article/details/18890283