（4）插入排序之二折半插入排序

时间：2011-04-24 来源：wang_gary

由于插入排序的基本操作是在一个有序表中进行查找和插入，这个“查找”操作可利用“折半查找”来实现，由此进行的插入排序称之为折半插入排序（Binary Insertion Sort）。时间复杂度为O(n^2)。理解：依次将每个待排序的记录插入到一个有序序列的合适位置。插入的位置是采用折半查找法确定的。

void CInsertionSort::BinaryInsertion(void)
{
    //元素0是哨兵。
    const int count = 9;
    int L[count] = {0, 49, 38, 65, 97, 76, 13, 27, 49};
    //对顺序表L作折半插入排序。
    for (int i = 2; i < count; i ++)
    {
        L[0] = L[i];
        int low = 1;
        int high = i - 1;
        while(low <= high)
        {
            int m = (low + high) / 2;
            if (L[0] < L[m])
                high = m - 1;
            else
                low = m + 1;
        }
        for (int j = i - 1; j >= high + 1; --j)
            L[j + 1] = L[j];
        L[high + 1] = L[0];
    }
    //打印排序结果。
    for (int i = 0; i < count; ++ i)
    {
        cout << L[i] << "\t";
    }
    cout << endl;
}

对于一个有序序列，采用折半查找的方式，可以提高查找的速度。那么折半插入法就是用这种方式来实现查找应插入到有序序列的位置。然后移动相应的记录，再插入到正确的位置。