1 #include <stdio.h>
2 int BInsertSort(int array[],int left,int right){ //接收主函数调用语句中的实参传到这里的形参里
3 int low,high,mid;
4 int temp;
5 for(int i=left+1;i<=right;++i){
6 temp=array[i]; //把第2个数(也就是下标1位置的数)存到temp临时变量里,即从第2个数开始往后的序列依次按照折半插入插入到第一个数的数列里(默认第一个数作为一个有序序列)
7 low=left; //将待插入的关键字要想插入到已经有序的序列中,需要找到插入位置,从此句往下为在有序序列中查找插入位置
8 high=i-1; //在有序序列中设置左右下标变量low和high
9 while(low<=high){ //当low和high交换位置时结束查找
10 mid=(low+high)/2;
11 if(array[i]<array[mid]) /*此while循环为折半查找算法*/
12 high=mid-1;
13 else //如果待插入关键字大于或等于下标为mid处的关键字,都是在mid处后面进行插入
14 low=mid+1;
15 }
16 for(int j=i-1;j>=low;--j) //把从low号位置及其后的关键字全部后移一个位置,把待插入的关键字放在low号位置
17 array[j+1]=array[j];
18 array[low]=temp;
19 }
20 return 0;
21 }
22 int main(){
23 int a[6]={10,9,3,5,4,2};
24 printf("排序前序列:");
25 for(int i=0;i<6;++i)
26 printf("%d\t",a[i]);
27 printf("\n");
28 BInsertSort(a,0,5); //调用BInsertSort函数,把待排序数组a,左下标0,右下标5传到形参
29 printf("排序后序列:");
30 for(int j=0;j<6;++j)
31 printf("%d\t",a[j]);
32 printf("\n");
33 return 0;
34 }