折半插入排序（Binary Insertion Sort）是对插入排序算法的一种改进，所谓排序算法过程，就是不断的依次将元素插入前面已排好序的序列中。
排序思想：有一组数据待排序，排序区间为Array[0]~Array[n-1]。将数据分为有序数据和无序数据，第一次排序时默认Array[0]为有序数据，Array[1]~Array[n-1]为无序数据。有序数据分区的第一个元素位置为low，最后一个元素的位置为high。
遍历无序区间的所有元素，每次取无序区间的第一个元素Array[i]，因为0~i-1是有序排列的，所以用中点m将其平分为两部分，然后将待排序数据同中间位置为m的数据进行比较，若待排序数据较大，则low~m-1分区的数据都比待排序数据小，反之，若待排序数据较小，则m+1~high分区的数据都比 待排序数据大，此时将low或high重新定义为新的合适分区的边界，对新的小分区重复上面操作。直到low和high 的前后顺序改变，此时high+1所处位置为待排序数据的合适位置。
时间复杂度：O(n^2)
稳定性：稳定。
#include<stdio.h>#include<stdlib.h>int *Array; /*Array是一个int 型地址，指向数组的首地址。*/int Count; /*Count用来存储所要排序的数字的数目。*//*建立未排序数组*/void CreateArray(){int i; /*创建数组必须用常量分配，而我们事先并不知道要处理的数据个数，所以用malloc动态分配数组单元。*/Array = (int *)malloc(sizeof(int)*Count); for (i = 0; i < Count; i++){printf("Please enter an integer of NO.%d to sort:n",i+1); scanf("%d",&Array[i]);}}/*输出已排序数组*/void Print(){int i;for (i = 0; i < Count; i++){printf(" %d ",Array[i]);}printf("n");}/*折半插入排序升序排列*/void BinaryInsertSortup(){int i,j,x,m; /*i,j均为循环变量，x用来存储当前待排序的数据，m充当比较区间的中点*/int low,high; /*low代表要与Array[i]进行比较的有序区间的第一个元素所在位置。 high代表要与Array[i]进行比较的有序区间的最后一个元素所在位置。*/for (i = 1; i < Count; i++){x = Array[i];low = 0; /*第一次划分有序比较区间，比较区间的第一个元素所在位置为0*/high = i-1; /*第一次划分有序比较区间，比较区间的最后一个元素所在位置为n-1*//*比较查找Array[i]合适插入的位置*/while (low <= high){m = (low + high)/2;if (x >= Array[m]){low = m+1;}else{high = m-1;}}/*确定好位置后，将位置之后的数据后移，插入待排序数据*/for (j = i-1;j > high; j--){Array[j+1] = Array[j];}Array[j+1] = x;}}/*折半插入排序降序排列*/void BinaryInsertSortdown(){int i,j,x,m; /*i,j均为循环变量，x用来存储当前待排序的数据，m充当比较区间的中点*/int low,high; /*low代表要与Array[i]进行比较的有序区间的第一个元素所在位置。 high代表要与Array[i]进行比较的有序区间的最后一个元素所在位置。*/for (i = 1; i < Count; i++){x = Array[i];low = 0; /*第一次划分有序比较区间，比较区间的第一个元素所在位置为0*/high = i-1; /*第一次划分有序比较区间，比较区间的最后一个元素所在位置为n-1*//*比较查找Array[i]合适插入的位置*/while (low <= high){m = (low + high)/2;if (x <= Array[m]){low = m+1;}else{high = m-1;}}/*确定好位置后，将位置之后的数据后移，插入待排序数据*/for (j = i-1;j > high; j--){Array[j+1] = Array[j];}Array[j+1] = x;}}int main(void){int i;printf("Please enter the number of Numbers to sort:n ");scanf("%d",&Count);CreateArray(); /*创建数组用来存储将要排序的数。*//*插入排序法*/BinaryInsertSortup(); /*折半插入排序*/printf("升序排列n");Print();BinaryInsertSortdown(); /*折半插入排序*/printf("降序排列n");Print();return 0;}图示：以i=4时为例：
第一步
第二步
第三步：
第四步：
第五步：
第六步：
第七步：