在前一篇插入排序：表插入中。我们用静态链表的存储方式。直接插入的策略，构建了一种新的插入排序算法：表插入。
有人可能会想到：相同是静态链表的形式，为什么不使用更高效的折半插入策略呢？这样的想法真的非常好，假设做到了。显然是极大的优化。
我在网上还真看到了相关的内容，大家可搜下《表插入方法的改进》，里面有此想法的介绍。这篇博客就是介绍表插入的还有一种实现：表折半插入。看完一定让你彻底理解它！
与一般的折半插入相比，有例如以下的几点变化：
- 为了实现折半查找，我们对静态链表的节点类型做了一些变化：加入了一个前驱指针。
它的意义非常显然，曾经是high=mid-1，在单向链表中我们是做不到的(事实上能够换种方式做到，只是相对麻烦)，于是加入一指向其前驱的指针。构成双向链表，方便进行此操作。
- while循环的结束条件，有所不同。这个要细致理解！
const int MAX=100;
typedef struct rec
{
int data;
int pre; //前驱
int next; //后继
}Rec;
void InsertSort(int a[], int n) //表折半插入
{
Rec *rec=new Rec[n+1];
for(int i=0; i<n; i++)
{
rec[i+1].data=a[i];
rec[i+1].next=rec[i+1].pre=0;
}
rec[0].data=MAX;
rec[0].next=rec[0].pre=1;
int low,high,mid;
int p,k,l;
for(int i=2; i<n+1; i++)
{
//依据下面的赋值，我们能够看出。这里使用的是左闭右闭区间
low=rec[0].next; //low指向最小的
high=rec[0].pre; //high指向最大的
l=i-1; //已有序的元素个数
while(low!=0 && high!=0 && rec[low].data<=rec[high].data) //循环结束条件得理解，特别是前两个条件。准确的是。第一个条件能够不要
{
mid=low;
k=1;
l/=2; // l>>=2 减半。为下次循环做好准备
while(k<l) //寻找mid位置
{
mid=rec[mid].next;
k++;
}
if(rec[i].data<rec[mid].data)
high=rec[mid].pre;
else
low=rec[mid].next;
}
//插入第i个节点。相似于双向链表的插入
rec[rec[low].pre].next=i;
rec[i].pre=rec[low].pre; //加入前驱指针的作用体如今这里
rec[i].next=low;
rec[low].pre=i;
}
//顺着next指针方向打印
printf("表折半插入排序后
");
p=rec[0].next;
while(p!=0)
{
printf("%-4d",rec[p].data);
p=rec[p].next;
}
printf("
");
}
可假设
rec[i].data<rec[mid].data,就有high=rec[mid].pre,即high=1.此时显然有rec[low]<rec[high],也就是说循环还得接着经进行下去。问题就出在这里！讲到这里，你应该明确：即使出现low为0,它也会违反第三条件：rec[low].data<=rec[high].data)(由于rec[0]的值域是最大的)。这就是为什么说，第一个条件low!=0能够去掉。