一、算法原理

折半插入排序是插入排序方法中一種，相比較與直接插入排序算法，減少了排序過程中比較次數，也是一種常用的排序算法。
折半插入排序算法基本原理是將折半查找方法與直接插入排序方法相結合，也就是在每一次插入新元素時，利用折半查找方法找到其待插入的位置。
下面Demo演示了折半插入排序的實現過程。

Demo：
假設有數組:

折半插入排序首先把第一個元素直接放到排好序的數組中，第二個元素可以使用直接插入排序法進行排序，從第三個元素開始進行插入排序。
第一趟排序：

第二趟排序：l =0表示左，h=1表示右，m=(l+h)/2=1表示中間，其位置如下表所示，元素arr[2]=3是待插入元素，首先將其緩存到t。

此時arr[m] < t，因此修改l為m+1=1，之后重新計算m=(l+h)/2=1

再次比較出現arr[m] > t，因此修改h為m-1=0,出現了h<l的情形，因此結束本趟的排序，記錄h的位置（h=0），然后把h+1位置的元素向后移動一位，將t的值插入到arr[h+1].

第三趟排序：將元素arr[3]緩存給t，然后重復第二趟排序的方法即可
第四趟排序和第五趟排序，同上述方法一樣，經過五趟排序之后，就完成了對該數組的折半插入排序。

二、折半插入排序算之C程序及測試

1. 折半插入排序

//將數組arr按照折半插入排序算法進行排序 
void BinInsertSort( int arr[], int n )
{
	int i, j, lo, mid, hi, t;
	//第二個元素做直接插入排序 
	if( arr[1] < arr[0] )
	{
		t = arr[0];
		arr[0] = arr[1];
		arr[1] = t;
	}
//從第三個元素開始進行折半插入排序
	for( i = 2; i < n; i++ )
	{
		t = arr[i];
		lo = 0;
		hi = i-1;
		//折半查找插入位置 
		while( lo <= hi ) 
		{
			mid = int( (lo + hi) / 2 );
			if( t < arr[mid] )
			{
				hi = mid - 1;
			}
			else if( t > arr[mid]  ) 
			{
				lo = mid + 1;
			}
			else
			{
				hi = mid;
				break;
			}
		}
		//從hi+1位置到i-1，向后依次移動元素，空出hi+1位置存儲新插入的元素 
		for( j = i - 1; j >= hi + 1; j-- )
		{
			arr[j + 1]= arr[j];
		}
		arr[hi + 1] = t;
	}
}

2.完整的代碼（僅供參考）

#include"stdio.h"
void BinInsertSort( int arr[], int n );

int main()
{
	int arr[] = { 4, 1, 3, 5, 4, 2 };
	int n = 6;
	printf( " Initial Array  : " );
	for( int j = 0; j < n; j++  )
	{
		printf( "%5d", arr[j] );
	}
	printf( "\n" );
	BinInsertSort( arr, n );
	return 0;
}
//將數組arr按照折半插入排序算法進行排序 
void BinInsertSort( int arr[], int n )
{
	int i, j, lo, mid, hi, t;
	//第二個元素做直接插入排序 
	if( arr[1] < arr[0] )
	{
		t = arr[0];
		arr[0] = arr[1];
		arr[1] = t;
	}
	printf( " No. 1 time sort: " );
	for( j = 0; j < n; j++  )
	{
		printf( "%5d", arr[j] );
	}
	printf( "\n" );
	//從第三個元素開始進行折半插入排序
	for( i = 2; i < n; i++ )
	{
		t = arr[i];
		lo = 0;
		hi = i-1;
		//折半查找插入位置 
		while( lo <= hi ) 
		{
			mid = int( (lo + hi) / 2 );
			if( t < arr[mid] )
			{
				hi = mid - 1;
			}
			else if( t > arr[mid]  ) 
			{
				lo = mid + 1;
			}
			else
			{
				hi = mid;
				break;
			}
		}
		//從hi+1位置到i-1，向后依次移動元素，空出hi+1位置存儲新插入的元素 
		for( j = i - 1; j >= hi + 1; j-- )
		{
			arr[j + 1]= arr[j];
		}
		arr[hi + 1] = t;
//向屏幕輸出每趟排序結果
		printf( " No. %d time sort: ", i );
		for( j = 0; j < n; j++  )
		{
			printf( "%5d", arr[j] );
		}
		printf( "\n" );
	}
}

3.測試用例
測試一：

測試二（有相同數據）：