折半插入排序

• • 基本思想
  • 算法分析
  • 算法实现

基本思想

当插入第 i ( i > = 1 ) i(i>=1) i(i>=1)个元素的时候，前面的 V [ 0 ] , V [ 1 ] , . . . , V [ i − 1 ] V[0],V[1],...,V[i-1] V[0],V[1],...,V[i−1]个元素已经排好序，然后使用折半查找 V [ i ] V[i] V[i]的插入位置

算法分析

排序码比较次数
K C N = ∑ i = 1 n − 1 └ l o g 2 i + 1 ┘ ≈ n l o g 2 n KCN = \sum_{i=1}^{n-1}\llcorner log_2i+1 \lrcorner \approx nlog_2n KCN=i=1∑n−1​└log2​i+1┘≈nlog2​n

算法实现

//折半插入排序
//@param arr 待排序数组
//@param len 待排序数组长度
void BinaryinsertionSort(int arr[], int len)
{
	int tailIndex = 0; //用于指示已经排好序列结尾的下标
	int curIndex = 0; //用于指示待排数字的下标

	int curValue = 0; //保存待排关键字

	int low = 0, high = 0; //折半查找的范围

	int m;
	for (curIndex = 1; curIndex < len; curIndex++)
	{
		curValue = arr[curIndex];
		low = 0; high = curIndex - 1;

		//借助折半查找来找到应插入元素的位置
		while (low <= high)
		{
			m = (low + high) / 2;
			if (arr[m] > curValue)
				high = m - 1;
			else
				low = m + 1;
		}

		for (tailIndex = curIndex - 1; tailIndex >= high + 1; tailIndex--)
			arr[tailIndex + 1] = arr[tailIndex];
		arr[tailIndex + 1] = curIndex;
	}
}