（3）插入排序之一直接插入排序

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

直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。时间复杂度为O(n^2)。理解：依次将每个待排序的记录插入到一个有序序列的合适位置。插入的位置是和有序序列的每一个元素进行比较，然后确定的。

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