折半插入排序

    直接插入排序在查找待排序记录位置时使用的是顺序查找，所以在有序序列中查找待插入记录的位置时可以使用折半查找法。

    基本思想：因为R[1..i-1]是一个按关键字有序的序列，可以利用折半查找定位记录R[i]在R[1..i]中插入位置，再将插入位置开始的记录顺序后移一个位置，将R[i]插入到指定位置。

    程序：

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <time.h>
#define MAXSIZE 10
typedef struct
{
 int length;
 int arr[MAXSIZE+2];
}list;
void insert(list* p)
{
 int i,j;
 int low,high,mid;
 for (i = 2; i <= p->length; i += 1)
 {
  p->arr[0] = p->arr[i];
  low = 1;
  high = i-1;
  while (low <= high)
  {
   mid = (low+high) / 2;
   if (p->arr[0] <= p->arr[mid])
   {
    high = mid-1;
   }
   else
   {
    low = mid+1;
   }
  }
  for (j = i-1; j >= high + 1; j --)
  {
   p->arr[j+1] = p->arr[j];
  }
  p->arr[high+1] = p->arr[0];
 }
}
int main()
{
 int i;
 list *plist;
 plist = (list*)malloc(sizeof(list));
 plist->length = MAXSIZE;
 plist->arr[MAXSIZE+2] = 0;
 srand((unsigned int)time(NULL));
 for (i = 1; i < MAXSIZE+1; i += 1)
 {
  plist->arr[i] = (rand() % 100);
  printf("array before:%d\n", plist->arr[i]);
 }
 insert(plist);
 printf("\n");
 for (i = 1; i < MAXSIZE+1; i += 1)
 {
  printf("array after:%d\n", plist->arr[i]);
 }
 return 0;
}

算法分析：折半插入排序比直接插入排序明显减少了关键字之间的比较次数，但记录的移动次数没有改变。因此，折半插入排序的时间复杂度仍为O（n*n），但是因为减少了比较次数，所以该算法仍然比直接插入排序好一点。