二分插入排序

当n较大时，二分插入排序的比较次数比直接插入排序的最差情况好得多，但比直接插入排序的最好情况要差，所以当元素初始序列已经接近升序时，直接插入排序比二分插入比较次数少。

#include <stdio.h>


// 分类 -------------- 内部比较排序

// 数据结构 ---------- 数组

// 最差时间复杂度 ---- O(n^2)

// 最优时间复杂度 ---- O(nlogn)

// 平均时间复杂度 ---- O(n^2)

// 所需辅助空间 ------ O(1)

// 稳定性 ------------ 稳定



void InsertSortDichotomy( int A[], int n )
{
    int i, j, get, left, mid, right;
    for( i = 1; i < n; i++ )    // 类似抓扑克牌排序
    {
        left = 0;               // 拿在左手上的牌总是排序好的，所以可以用二分法
        right = i - 1;         // 手牌左右边界进行初始化
        get = A[i];           // 右手抓到一张扑克牌
        
        while( left <= right ) // 采用二分法定位新牌的位置
        {
            mid = (left + right)/2;
            if( A[mid] > get )
                right = mid - 1;
            else
                left = mid + 1;
        }
        
        for(j = i-1; j >= left; j--)  // 将欲插入新牌位置右边的牌整体向右移动一个单位
        {
            A[j+1] = A[j];
        }
        A[left] = get;  // 将抓到的牌插入手牌
    }
}

int main()
{
    int A[] = { 8, 5, 2, 6, 9, 3, 1, 4, 0, 7 }; // 从小到大插入排序
    int n = sizeof(A) / sizeof(int);
    
    InsertSortDichotomy( A, n );
    
    int i;
    printf("二分插入排序结果：");
    for( i = 0; i < n; i++ )
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    
    return 0;
}