排序之二分法折半插入排序

 1 //二分法折半插入排序
 2 /*折半插入算法思想
 3 1、初始化：设定有序区为第一个元素，设定无序区为后面所有元素
 4 2、依次取无序区的每个元素
 5 3、通过二分法查找有序区,返回比这个数小的最大数
 6 4、保留此位置数据
 7 5、从此位置的元素到有序区的最后一个元素，依次后移
 8 6、用保留的数据填充此位置
 9 */
10 void sortByInsertHalf(int array[],int arraySize)
11 {
12     int iMax,iMid,iMin;
13     for(int i=1;i<arraySize;i++)
14     {
15         int temp = array[i];
16         iMax = i-1;
17         iMin = 0;
18         while(iMin<=iMax)
19         {
20             iMid = (iMax+iMin)/2;
21             if(array[iMid]>=temp)
22             {
23                 iMax = iMid-1;
24             }
25             else
26             {
27                 iMin = iMid+1;
28             }
29         }
30         for(int j=i-1;j>=iMax+1;j--)
31         {
32             array[j+1] = array[j];
33         }
34         array[iMax+1] = temp;
35     }
36 }
37 
38 void print(int a[],int length)
39 {
40     for(int i=0;i<length;i++)
41     {
42         printf("%d ",a[i]);
43     }
44     printf("\n");
45 }
46 
47 int main()
48 {
49     int a[10] = {7,2,8,3,9,10,15,11,20,17};
50     sortByInsertHalf(a,sizeof(a)/sizeof(int));
51     print(a,sizeof(a)/sizeof(int));
52     return 0;
53 }