折半插入排序又称为二分法插入排序。此排序算法的”折半“是指无序表中的元素要插入到有序表中，该插到哪个位置？在有序表中寻找插入位置的方法是二分查找法。所以叫做折半插入。
i
0
1 2
3
4
5
6 7
8 9
原始序列 21
25
49
25*
16
08
62
38
71
54
不再一趟趟分析，从第六趟排序结束后举例说明。
i
0
1
2
3
4
5
6
7
8
9
第六趟结束
08
16
21
25
25*
49
62
38
71
54
第七趟开始，从无序表中取出a[7],先跟有序表的最后一个比较，发现比62小，说明a[7]肯定要放到a[6]前边。开始使用二分查找法在有序表中找a[7]的插入位置。有序表的范围是0—i-1。用low=0，high=i-1表示。先把a[7]存入临时变量temp。循环条件（low<=high)：求有序表的中间位置mid=（low+high)/2;拿temp和a[mid]比较，如果temp>a[mid],说明temp（即a[7])的最终插入位置在
mid——high之间，则将low = mid + 1;如果temp<a[mid],显然插入位置在有序表的low——mid之间，将high = mid -1;继续在[low,high]之间二分查找直到low>high,跳出循环。此时low的位置是temp最终的插入位置。
【上述并没有考虑temp==a[mid]的情况。当等于时，是该high=mid-1,还是说low = mid + 1呢？（或者说是temp>=a[mid]还是temp<=a[mid]?)这个等号的归属决定了折半插入排序的稳定性。在稳定与不稳定之间，我们当然希望算法是稳定的。哪种情况是稳定的？假设序列是这样的：{
08 16 21 25 38 49 62
25*}红色是有序的。low = 0, high = 6 ，mid = 3。即a[mid]==temp(25*),如果用temp>=a[mid]时，low = mid + 1;此时 temp的插入位置一定在{38,49,62}这几个位置上，这保证了25*一定出现在25 的右边，也就保证了排序的稳定。反之，出现在25的左边，排序不稳定。你觉得是这个理儿不？
这一段话是自己琢磨的，不知道对不对，你们自己找些数试试对不对。还有二分查找结束时，temp的位置是low，而不是high。
】
二分查找结束，找到了插入位置 i = 5 ，此时需要做的是将[5,6]的元素依次移动到[6,7],然后把temp放到a[low]j即a[5]。算法结束。
依旧是vs2008 c++
1、Sort.h
#pragma once
typedef struct node{
int key;
}DataType;
typedef struct {
DataType *elem;
int maxSize;
int num;
}DataList;
class Sort
{
public:
Sort(void);
~Sort(void);
void binaryInsertSort(DataList &L);//折半插入排序
};
2、Sort.cpp
void Sort::binaryInsertSort( DataList &L )
{
int i = 0, j = 0, low = 0, high = 0, mid = 0;
DataType temp;
for(i = 1; i < L.num; i++)
{
if(L.elem[i].key < L.elem[i-1].key)
{
low = 0;
high = i-1;
temp = L.elem[i];
while(low <= high)
{
mid = (low + high)/2;
if(temp.key < L.elem[mid].key)
high = mid - 1;
else
low = mid + 1;
}
for(j = i-1; j >= low; j--)
{
L.elem[j+1] = L.elem[j];
}
L.elem[low] = temp;
}
}
}
上一篇直接插入排序中没有给出 初始化L和显示L中元素的方法。此处给出，后续都不在赘述。
void initDataList(DataList &L)
{
L.maxSize = 20;
L.elem = new DataType[L.maxSize];
if(NULL == L.elem)
{
cout << "存储分配失败\n";
exit(1);
}
srand(time_t(NULL));
L.num = 10;
for(int i = 0; i < 10; i++)
{
L.elem[i].key = rand()%100;
}
}
void display(const DataList &L)
{
cout << "DataList中的数据\n";
for(int i = 0; i < L.num; i++)
{
cout << L.elem[i].key << " ";
}
cout << endl;
}
分析：
最好情况是列表有序，只需比较n-1次，无需移动。
最坏情况是列表逆序，用二分查找法，比较NlogN。移动次数O(n^2)。
时间复杂度O(NlogN)。
稳定排序。
辅助空间O(1)。