折半插入排序

#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <vector>
#include <algorithm>
#include "dbg.h"
using namespace std;

void binaryInsetionSort(int R[], int len)
{
    // 假设初始有序序列为R[0]
    for (int i = 1; i < len; i++)
    {
        int temp = R[i];
        int low = 0, high = i - 1; // 设置折半查找范围
        while (low <= high)        // 开始在有序序列中进行折半查找,
                                   //low为最终查找到的插入位置
        {
            int mid = low + (high - low) / 2;
            if (R[mid] > temp)
                high = mid - 1;
            else
                low = mid + 1;
            
        }

        for (int j = i - 1; j >= low; j--)
            R[j + 1] = R[j]; // 后移，将插入位置空出来
        R[low] = temp;       // 插入元素
    }
}

int main(int argc, char *argv[])
{
    int R[] = {1, 3, 2, 18, 3, 28, 23, 38, 7, 8};
    cout << "Before sorting = " << endl;
    dbg(R);
    int len = sizeof(R) / sizeof(R[0]);
    cout << "After sorting  = " << endl;
    binaryInsetionSort(R, len);
    dbg(R);
    return 0;
}