二分法插入排序，简称二分排序，是在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。

算法步骤

1、二分法查找插入位置

如果R<R[m]成立，那右指针就要向左移动中间指针一位，否则，左指针要向右移动中间指针一位。反复查找，直到左指针大于右指针时停止。

2、后移，有点迷惑，什么时候需要后移呢？有哪些记录需要移动呢？

虽然我们很清楚的知道，我们需要后移那些排序码大于R的记录，但难免会问自己这样几个问题。其实它相当于需要移动从i-1到左指针的记录。

3、插入

由1中得到的左指针其实就是元素要插入的位置。

动图演示

image

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

//交换数值
void swap(int *a,int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
//打印数组
void printArray(char msg[],int arr[],int len){
    printf("%s:",msg);
    for (int i = 0; i < len; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
}
//二分法插入排序
void binary_insert(int a[],int len){
    for(int i=1;i<=len-1;i++){
        int left=0;
        int right=i-1;
        int temp=a[i];
        //如果a[i]比最大值还大或者相等，则不交换位置,跳过二分查找
        if(temp>=a[right]){
            continue;
        }
        //left>right时循环终止
        while(left<=right){
            //折半
            int mid=(left+right)/2;
            if(temp<a[mid]){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        printf("要插入的数据：a[%d]=%d\n",i,temp);
        printArray("插入数据前",a,len);
        //大于等于left的位置后移一位
        for(int j=i-1;j>=left;j--){
            a[j+1]=a[j];
        }
        a[left]=temp;
        printArray("插入数据后",a,len);
        printf("\n");
    }
}
int main()
{
    int len=10;
    int arr[len];
    srand((unsigned)time(NULL));
    //随机生成长度为"len"的数组
    for(int i=0;i<len;i++){
        arr[i]=rand()%200;
    }
    printArray("未排序前",arr,len);
    binary_insert(arr,len);
    printArray("二分法插入排序",arr,len);
    //防止windows下控制台窗口闪退
    int s;
    scanf("%d",&s);
    return 0;
}

运行结果：

未排序前:96 109 174 33 132 196 181 52 68 57
要插入的数据：a[3]=33
插入数据前:96 109 174 33 132 196 181 52 68 57
插入数据后:33 96 109 174 132 196 181 52 68 57
要插入的数据：a[4]=132
插入数据前:33 96 109 174 132 196 181 52 68 57
插入数据后:33 96 109 132 174 196 181 52 68 57
要插入的数据：a[6]=181
插入数据前:33 96 109 132 174 196 181 52 68 57
插入数据后:33 96 109 132 174 181 196 52 68 57
要插入的数据：a[7]=52
插入数据前:33 96 109 132 174 181 196 52 68 57
插入数据后:33 52 96 109 132 174 181 196 68 57
要插入的数据：a[8]=68
插入数据前:33 52 96 109 132 174 181 196 68 57
插入数据后:33 52 68 96 109 132 174 181 196 57
要插入的数据：a[9]=57
插入数据前:33 52 68 96 109 132 174 181 196 57
插入数据后:33 52 57 68 96 109 132 174 181 196
二分法插入排序:33 52 57 68 96 109 132 174 181 196