1. 算法介绍
2. 源码
3. 总结

一.算法介绍

      折半插入排序算法是在直接插入排序算法的基础上进行的改进。由于直接插入排序算法分为查找和插入两个部分的操作，而在直接插入排序算法中进行查找的算法是依次访问每个元素的，这样我们就可以对查找进行折半查找来改进算法的效率。

折半查找我将它分为两个部分，一部分是需要折半查找的元素为偶数个的情况，另一个是需要折半查找的元素为奇数个的情况。

• 偶数个

     如果是偶数个元素，那么进行折半的时候，就会出现中间数为两个的情况。如图所示：

       第一个元素n表示这个数组中含有的元素个数，假设前四个元素已经排序了，我们将要对第五个元素2进行折半插入排序。我们将那个indexlow设置为1，代表元素1，将indexhigh设置为4，代表元素5.这样我们折半的时候，中间的元素就有两个：下标为2的元素3和下标为3的元素4.这样确定待插入的元素的下标就需要分为三种情况：

      (1).待插入元素小于中间左边的元素3（如本例子）;

      (2).待插入元素大于等于中间右边的元素4；

      (3).待插入元素在中间两个元素的中间；

对于这三种情况需要分别进行处理。

• 奇数个

     如果元素为奇数个的话，那么进行折半的时候，中间数就只有一个，这样就自然分为两种情况了大于或等于中间的元素，和小于中间元素的情况分别进行处理。

当通过以上的处理获得了待插入元素需要插入的坐标后，我们就进行移动元素的操作，将待插入的元素插入到我们获得的那个位置即可。如此反复，直到将所有元素排序完毕。

二.源码

/************************************************************************/
/* 折半插入排序算法                                                     */
/************************************************************************/
#include<iostream>
#define MAX_SIZE 20

using namespace std ;

void sort(int array[MAX_SIZE])
{
	if (array[2]<array[1])//对前两个元素特别处理
	{
		int temp = array[2];
		array[2]=array[1];
		array[1]=temp;
	}

	for (int i = 3 ; i <= array[0];i++)//对后面所有元素进行如下处理，0号元素存放了数组中有多少元素
	{
		int indexhigh = i-1 ;
		int indexlow = 1 ;
		int m = 0 ;//m用来保存将要插入的值的位置
		while (true)
		{
			if ((indexhigh+indexlow+1)%2 == 0)//如果待插入的值前面有偶数个值的时候
			{
				m=(indexlow+indexhigh)/2;//为偶数时，将m设置为中间较小的那个值
				if (array[i]<array[m])//待插入的值小于左边的值的时候
				{
					if (m==1)//如果是要插在第一个元素就退出，不需要在进行判断了
					{
						break;
					}
					indexhigh=m;//否则将要折半查找的高下标赋值为m
				}
				if (array[i]>=array[m+1])//如果待插入值大于右边的值
				{
					if (m+1==i-1)//如果待插入的值大于前面所有的元素
					{
						m=i;
						break;
					}
					indexlow=m+1;//否则就将右边值的下标赋给低下标值
				}
				if (array[i]>array[m]&&array[i]<=array[m+1])//如果待插入的值在左右两个值中间
				{
					m=m+1;break;//就将右边值的下标作为待插入值的下标，并退出循环
				}
			}
			else//如果需要折半的元素有奇数个
			{
				m=(indexlow+indexhigh)/2;
				if (array[i]<=array[m])//这里一定是要小于等于，如果等于去掉了，
										//那么当排序中有相同的元素的时候就会死循环
				{
					indexhigh=m;
				}
				else
				{
					indexlow=m;
				}
			}
		}

		for (int j = i ; j>m ; j--)//移动元素
		{
			int temp = array[j];
			array[j]=array[j-1];
			array[j-1]=temp;
		}
	}
}

//测试程序
int main()
{
	int array[MAX_SIZE];
	array[0]=6 ;
	array[1]=3;
	array[2]=4;
	array[3]=1;
	array[4]=3;
	array[5]=11;
	array[6]=2;

	sort(array);

	for (int i = 1 ;i<=array[0];i++)
	{
		cout<<array[i]<<endl;
	}

	int i;
	cin>>i;

	return 0 ;
}

以上代码存在不足只处，不过基本上可以使用了。

三.总结

       进行代码调试时，一步一步的执行很重要。同时我们需要先清清楚楚的弄明白算法的整个过程和细节，不能只有一个大概的认识，因为那样对编程时的细节很难处理。