利用二分法实现插入排序算法（二分法使用递归来实现）

// Algrithms.cpp : 定义控制台应用程序的入口点。
//
//使用二分法来完成插入排序，并且使用递归算法来完成二分法
#include "stdafx.h"
int Binary_Divide(int A[], int low, int height, int key){
    //递归终止的条件为输入的low>输入的height，这时所寻找到的位置为low的左边或者右边
    //这时只需要判断key和A[low]之间的大小就可以判断出key所应该放置的位置
    if (low > height)
    {
        if (key > A[low])
        {
            return low + 1;//如果key比A[low]大，那么key就放置在A[low]的下一个位置上面
        }
        else{
            return low;//如果key比A[low]小，那么key就放置在A[low]的位置上面（因为之后的程序会将这个位置空出来）
        }
    }
    if (A[(low + height) / 2] > key)
    {
        Binary_Divide(A, low, (low + height) / 2 - 1, key);
    }else
    {
        Binary_Divide(A, (low + height) / 2 + 1, height, key);
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    int a[11] = { 6, 10, 13, 3, 7, 20, 24, 100, 1, 3, 6 };//被排序的数组
    int array_length = sizeof(a) / sizeof(a[0]);//数组大小
    int key;//关键字
    //将A[n]插入到已经排好序的前n-1个数当中
    for (int i = 1; i < array_length; i++)
    {
        key = a[i];
        int j = i - 1;
        int position = Binary_Divide(a, 0, j, key);//二分法寻找key所应该处的位置
        //将position（包括position）之后直到j的数往后挪动一个位置
        while (j >= 0 && j>=position)
        {
            if (a[j]>key)
            {
                a[j + 1] = a[j];
            }
            j--;
        }
        a[position] = key;//将关键字放置在正确的位置上面
        //每排列好一个元素的位置就将数组打印出来
        for (int k = 0; k < array_length; k++)
        {
            printf("%d ", a[k]);
        }
        printf("%d
",position);//打印所找到的合适位置
    }
    getchar();
    return 0;
}