HalfInsertSort

public class 二分插入 {
	void HalfInsertSort(int a[], int len)
	{
	     int i, j,temp;
	     int low, high, mid;
	     for (i=1; i<len; i++)
	     {
	          temp = a[i];/* 保存但前元素 */
	          low = 0;
	          high = i-1;
	          while (low <= high) /* 在a[low...high]中折半查找有序插入的位置 */
	          {
	               mid = (low + high) / 2; /* 找到中间元素 */
	               if (a[mid] > temp)  /* 如果中间元素比但前元素大，当前元素要插入到中间元素的左侧 */
	               {
	                high = mid-1;
	               }
	               else    /* 如果中间元素比当前元素小，但前元素要插入到中间元素的右侧 */
	               {
	                low = mid+1;
	               }
	          }       /* 找到当前元素的位置，在low和high之间 */
	          for (j=i-1; j>high; j--)/* 元素后移 */
	          {
	           a[j+1] = a[j];
	          }
	          a[high+1] = temp; /* 插入 */
	     }
	}
}