插入排序之“折半插入排序”（C++实现）

定义

由于直接插入排序产生了有序区，所以可以采用折半查找法找到插入的位置，这样的插入排序称为折半插入排序
因此折半插入有一个重要的条件就是元素大小排列有序（从大到小或从小到大）

实现

void binInsertSort(int R[], int n)
{
    int i, j, low, high, mid;
    int tmp;
    for (i = 1; i < n; i++)
    {
        if (R[i] < R[i - 1])
        {
            tmp = R[i];
            low = 0;
            high = i - 1;
            while (low <= high)//折半查找
            {
                mid = (low + high) / 2;
                if (tmp < R[mid])
                {
                    high = mid - 1;
                }
                else
                {
                    low = mid + 1;
                }
            }

            for (j = i - 1; j >= high + 1; j--)//集中进行元素后移
            {
                R[j + 1] = R[j];
            }
            R[high + 1] = tmp;//插入tmp
        }
    }
}

测试

int main()
{
    int R[] = { 8,6,1,3,4,9 };
    binInsertSort(R, 6);
    for (int i = 0; i < 6; i++)
    {
        cout << R[i] << "  ";
    }
    return 0;
}

总结

折半插入排序时直接插入排序的升级版