利用二分法實現插入排序算法（二分法使用遞歸來實現），二分法遞歸

利用二分法實現插入排序算法（二分法使用遞歸來實現），二分法遞歸

      最近在看《算法導論》這本書，在練習題當中發現了這樣的一個問題：使用二分查找法來實現插入排序，由於之前的內容當中有講解二分法的遞歸實現，所以在這便將它們結合起來希望解決這個問題。閒話不多說了，直接上代碼：

// 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\n",position);//打印所找到的合適位置
    }
    getchar();
    return 0;
}

    算法思路很簡單，無非是將原來的線性查找被排序元素的合適的位置的部分換成了使用二分法來查找合適的位置，之前困擾我很久的是遞歸終止情況的判斷。在學習二分查找的時候，我們知道，如果一個數不存在於一個數組當中的話，二分法會因為所輸入的數組下界大於上界而終止遞歸，而在本算法查找位置的時候，二分法的這種遞歸終止的性質會導致我們找到一個距離“適合位置”最近的點，所以這個點和關鍵字之間大小的判斷就可以傳輸回正確的位置了。

菜鳥一枚，第一次發博客，還請園裡面的大神們多多指教。