折半插入排序binary insertion sort)是對直接插入排序算法的一種改進，由於排序算法過程中，就是不斷的依次將元素插入到前面已排好序的序列塊中。由於前半部分為已排好的序列，這樣我們不用按順序從後往前）依次尋找插入點，可以采用折半查找的方法來加快尋找插入點的速度。
具體操作：
在將一個新元素插入到已排好序的數組的過程中，尋找插入點時，將待插入區域的收元素設置為a[low],末元素設置為a[high]，令m=(low+high)/2，讓a[m]與待插值元素做比較，如果待插值元素較大，則a[m+1]到a[high]為新的插入區域，否則a[low]到a[m-1]為新的插入區域。如此直到low<=high不成立。然後將此位置之後的元素後移一位，並將待插入元素插入a[high+1]；
#include <stdio.h>
#include <stdlib.h>
void swap(int arr[] ,int i, int j)
{
int temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void InsertSort(int arr[], int n)
{
int i;
for(i=1;i<n;i++) //循環從第2個數組元素開始，移位arr[0]作為最初已排序部分
{
int j;
int low = 0; //有序序列的最低位
int high = i - 1; //有序序列的最高位
int temp = arr[i];
while(low <= high)
{
int m = (low + high)/2;
if(temp < arr[m])
high = m - 1;
else
low = m + 1;
}
for(j = i-1; j>high; j--)
arr[j+1] = arr[j];
arr[high+1]=temp;
}
}
void print(int arr[], int n)
{
int i;
for(i=0; i<n; i++)
{
printf("%d ",arr[i]);
}
printf("\n");
}
int main()
{
int arr[]={9, 1, 5, 8, 3, 7, 4, 6, 2};
int n = sizeof(arr)/sizeof(arr[0]);
printf("排序前：\n");
print(arr, n);
InsertSort(arr,n);
printf("排序後：\n");
print(arr, n);
system("pause");
return 0;
}
本文出自 “李海川” 博客，請務必保留此出處http://lihaichuan.blog.51cto.com/498079/1282132
