1.排序原理
折半插入排序法是对直接插入排序法的改进，直接插入排序法(http://blog.csdn.net/whzhaochao/article/details/12953741)，是在前面已排好序的序列中顺序查找要插入的位置，折半插入排序法则是用二查找法找到要插入的位置，然后插入。
2.代码
#include <stdio.h>
void printArray(int a[],int size){
printf("数组为：[%d] ",a[0]);
for (int i=1;i<size;i++)
{
printf(" %d ",a[i]);
}
printf("
");
}
void main()
{
//a[0]为监视哨
int a[8]={0,38,65,97,76,13,27,49};
for (int i=2;i<=7;i++)
{
printf(" i=%d ",i);
printArray(a,8);
//将要插入的数放监视哨
a[0]=a[i];
int low=1,high=i-1;
//while循环用二分查找法找到要插入的位置为 high+1
while(low<=high){
int m=(low+high)/2;
if (a[0]<a[m])
{
high=m-1;
}else{
low=m+1;
}
}
printf("
%d要插入%d位置",a[0],a[high+1]);
if (i-1>=high+1)
{
printf("
%d到%d,要向前移一位
",a[high+1],a[i-1]);
}
//将 high+1到i-1位置数据移到 high+2到i位置
for (int j=i-1;j>=high+1;--j)
{
a[j+1]=a[j];
}
// high+1插入要插入的数据
a[high+1]=a[0];
}
printf("结果 ");
printArray(a,8);
}
3结果
i=2 数组为：[0] 38 65 97 76 13 27 49 65要插入65位置 i=3 数组为：[65] 38 65 97 76 13 27 49 97要插入97位置 i=4 数组为：[97] 38 65 97 76 13 27 49 76要插入97位置 97到97,要向前移一位 i=5 数组为：[76] 38 65 76 97 13 27 49 13要插入38位置 38到97,要向前移一位 i=6 数组为：[13] 13 38 65 76 97 27 49 27要插入38位置 38到97,要向前移一位 i=7 数组为：[27] 13 27 38 65 76 97 49 49要插入65位置 65到97,要向前移一位 结果 数组为：[49] 13 27 38 49 65 76 97