折半插入排序算法详解之C语言版

一、算法原理

折半插入排序是插入排序方法中一种，相比较与直接插入排序算法，减少了排序过程中比较次数，也是一种常用的排序算法。
折半插入排序算法基本原理是将折半查找方法与直接插入排序方法相结合，也就是在每一次插入新元素时，利用折半查找方法找到其待插入的位置。
下面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.测试用例
测试一：

测试二（有相同数据）：