插入排序--折半插入排序（来一来，看一看，走过路过，不要错过）-Toy模板网

这篇具有很好参考价值的文章主要介绍了插入排序--折半插入排序（来一来，看一看，走过路过，不要错过）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

人生没有彩排，每天都是现场直播，不仅收视率低，而且工资不高。

一.前言

插入排序根据查找插入位置的方式不同可以分为三类：按顺序法查找插入位置的——直接插入排序；按折半法也叫二分法查找插入位置的——折半插入排序;缩小增量多遍插入排序的——希尔排序。本文探讨有关折半插入排序的知识。

二.思想及操作分析

思想：
借助二分查找的思想，先查找插入位置，再移动数据，最后插入到正确的位置。
我们都知道直接插入排序是一个边比较边移动的过程，而折半插入排序是先确定插入的位置，再来进行移动。
插入排序的效率是由比较的次数和移动的次数共同决定的，而折半插入排序就是通过降低比较的次数来提高排序的效率。一起看看是如何进行操作的。

操作图解分析：
有一组数据如下，现在我们需要将这组数据按从小到大进行排序。
插入排序--折半插入排序（来一来，看一看，走过路过，不要错过）
将这一组数据分为有序组（有颜色的）和无序组（没有颜色的），数据的第一个元素默认为有序，如下：

将无序组中1号位置的数据进行拷贝，同时将1号位置收编到有序组序列中。此处将被拷贝位置的数据进行抹去方便进行分析，如下：
插入排序--折半插入排序（来一来，看一看，走过路过，不要错过）
接着采用折半查找在有序组中查找插入位置，低地址端为有序组的第一个位置（记为：low），高地址端为有序组的最后一个有效元素的位置（记为：high）,中端地址为mid=（low+high）/2，如下：
插入排序--折半插入排序（来一来，看一看，走过路过，不要错过）
将94和mid所指位置上的元素进行比较，发现94>81,则low=mid+1，如下：

当high小于low时，则low所指的位置即为插入位置，low所指的位置即1号位置此时并没有有效数据则不需要进行移动，直接进行插入，如下：
插入排序--折半插入排序（来一来，看一看，走过路过，不要错过）

继续从无序中将2号位置的数据进行拷贝，同时将二号位置收编到有序组的序列，依旧抹去2号位置的数据如下：
插入排序--折半插入排序（来一来，看一看，走过路过，不要错过）
high指向有序组最后一个有效数据的位置，low指向有序组的第一个位置，mid为两者和的二分之一，如下：

将11和mid所指位置的元素进行比较，11<81,说明11要放在81的前面。high=mid-1，此时high变为-1，不大于low则low所指的位置即为要插入的位置。而此时low所指的位置存在有效元素，那么我们需要将有序组中low所指位置的数据及其后面位置的数据整体移动一个位置，如下：
插入排序--折半插入排序（来一来，看一看，走过路过，不要错过）
将11插入到low所指的位置中，如下：

重复上面的操作，直至整个数据变为有序。给出最终的结果，如下：

每一次将无序组中的元素插入到有序组，都是通过二分查找法确定该元素会插入到有序组的哪一个位置后，再看该位置有没有被有效元素占据，没有就直接插入，有则将该位置元素及其后面位置的元素整体移动一个位置，再进行插入。

三.代码设计

基本步骤：
1.将数据进行分组，有序组和无序组；
2.从无序组中拷贝第一个位置的数据，采用二分查找法查找出该元素将要插入到有序组的哪一个位置；
3.将查找到的位置中的数据及其后面的数据整体移动一个位置；
4.将数据插入到查找到的位置；
5.重复2、3、4直到整个数据变为有序。

大的方向可以将该算法分为三部分，第一部分：从无序组中取元素的操作；第二部分：采用二分查找法查找插入位置的操作；第三部分：移动元素空出插入位置，再将数据插入的操作。

四.代码实现

typedef int ElementType;
void BinaryInsertSort(ElementType array[], int size)
{
	int high;//高地址位置
	int low;//低地址位置
	int mid;//中端位置
	int i;//指示无序组中的元素位置
	int j;//指示有序组中的元素位置
	ElementType temp;//临时变量，用于拷贝数据
	for (i = 1; i < size; i++)//第一个位置默认有序
	{
		temp = array[i];//拷贝数据
		high = i - 1;//指向有序组中最后一个有效数据
		low = 0;//指向有序组中第一个数据位置
		while (low<=high)//采用二分查找，在有序组中找待插入元素的位置
		{
			mid = (low + high) / 2;//中间位置为low于high和的一半
			if (array[mid] < temp)//说明插入位置在mid的右边
			{
				low = mid + 1;//指向比较位置的后一个位置
			}
			else//说明插入位置在mid的左边
			{
				high = mid - 1;//指向比较位置的前一个位置
			}
		}
		for (j = i; j >=low; j--)//将查找的位置元素及其后面的元素整体移动一个位置
		{
			array[j] = array[j - 1];
		}
		array[low] = temp;//插入到正确位置
	}
}