折半插入排序

折半插入排序是根据折半查找法来查找插入位置的。
折半查找的一个基本条件是序列已经有序。而从直接插入排序中可以看出，每一次插入后，序列都是有序的，所以可以用折半插入排序来提高性能。

代码：

#include <iostream>
using namespace std;

void InsertSort(int array[], int n) {
  int i, j, temp, low, high, mid;
  for (i = 1; i < n; ++i) {
    temp = array[i];
    low = 0;
    high = i - 1;
    j = i - 1;

    while (low <= high) {
      mid = (low + high) / 2;
      if (temp < array[mid])
        high = mid - 1;
      else
        low = mid + 1;
    }

    for (j = i - 1; j >= low; --j)
      array[j+1] = array[j];

    array[low] = temp;
  }
}

void print_array(int array[], int n) {
  for (int i = 0; i < n; ++i)
    cout<<array[i]<<" ";
  cout<<endl;
}

int main() {
  int array[] = {38, 49, 27, 65, 76, 97, 13, };
  print_array(array, 7);
  InsertSort(array, 7);
  print_array(array, 7);

  return 0;
}

复杂度分析：

1. 时间复杂度：
与直接插入排序相比，折半插入排序在查找插入位置上所花的时间大大减少。但是从代码中可以看出，找到插入位置后，还需要将后面的进行移动，折半插入排序在关键字移动次数方面和直接插入排序是一样的，所以其时间复杂度和直接插入排序还是一样的，是O(n^2)。
但是折半插入的比较次数是一定的。

2. 空间复杂度：
和直接插入排序一样，为O(1)。