十大排序算法——二分插入排序法（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");  //為了防止控制台閃退用的
}
           

有說的不對的地方請各位大佬多多指教！