十大排序算法——二分插入排序法（C语言）

二分插入排序法

直接插入排序方法：直接插入排序法

比较着看可以加深印象

原理

按由大到小来说

同直接插入排序一样，也是分有序序列和无序序列，将待排序的无序序列插入到有序序列当中。

二分插入是把待插入数值先和有序序列的中间数值进行比较，如果比中间值大，就在中间值的左侧在找中间值进行比较，如果比中间值小，就在中间值的右侧在找中间值进行比较，直到找到合适的位置插入到有序序列中。

C语言代码

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

//type为 0 时排序从小到大，为 1 时排序从大到小
void Insertion(int a[],int n,int type)
{
    for ( int i = 1; i < n; i++)
    {
        int temp=a[i];  //临时待插入值
        int left=0;  //左侧边界值
        int right=i-1;  //右侧边界值
        while (left <= right)
        {
            int mid = (left+right) / 2;  //中间值
            if(type == 0 ? (a[mid] > temp) : (a[mid] < temp))
            {
                right = mid - 1;   //把右侧边界缩小，在中间值得左边进行寻找
            }
            else 
            {
                left = mid + 1;  //把左侧边界加大，在中间值得右边进行寻找
            }            
        }
        for ( int j = i-1; j >= left; j--)  //将left到i-1之间的数都往后移动一个位置
        //注意如果要插入的数比前面排好序的数都大或者都小,则不会进入到该循环内，则此时将不会有数进行位置的移动
        {
            a[j+1] = a[j];
        }
        a[left] = temp;      //将要插入的数值插入到合适位置       
    }    
}
void main()
{
    int a[10];
    int i;
    //请输入十个整数
    printf("请输入十个整数:\n");
    for ( i = 0; i <10; i++)
    {
        scanf("%d",&a[i]);
    }
    Insertion(a,10,1);  //调用二分插入排序法
    //输出结果
    for ( i = 0; i < 10; i++)
    {
        printf("%d \n",a[i]);
    }
     system("pause");  //为了防止控制台闪退用的
}
           

有说的不对的地方请各位大佬多多指教！