排序之四：二分插入

基本思想：因为 R[1..i-1] 是一个按关键字有序排列的有序序列，因此可以利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”，由此实现的插入排序称为二分插入排序。

void swap (int a[],int i,int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; }

void printA (int *a,int len) { int i; for (i = 0; i < len; i++) { printf (“%-4d”,a[i]); } printf (“\n”); }

//二分插入排序 int main() { int a[10] = {9,2,1,5,4,7,6,3,8,0}; int len = sizeof(a)/sizeof(a[0]);

int left,right,i,j,get;

for (i = 1;i < len; i++) { get = a[i]; left = 0; //左边界 right = i-1; //右边界

while (left <= right) { int mid = (left+right)/2; if (a[mid] > get) { right = mid - 1; } else { left = mid + 1; } }

for (j = i-1; j >= left; j–) { a[j+1] = a[j]; } a[left] = get; }

printA (a,len); return 0;

}