算法导论 - 插入排序

老王

对于少量元素的排序，插入排序是一个有效的算法。插入排序的工作方式就像是许多人排序一手扑克牌，开始时，我们的左手为空并且桌子上的牌面向下；然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置；为了找到一张牌的正确位置，我们从右到左将它与已经在左手中的每张牌进行比较；最终，拿在左手上的牌是排序好的。

输入：n个数的一个序列<a1, a2,..., an>。

输出：输入序列的一个排列<a1', a2',..., an'>，满足a1'≤a2'≤...≤an'。

[C++] 纯文本查看 复制代码

    int arrInt[] = { 5, 4, 3, 2, 1, 10, 9, 8, 7, 6, -1, -2, -3, -4, -5 };
    size_t nCount = sizeof(arrInt) / sizeof(arrInt[0]);

    // 插入排序
    int nMax;
    size_t j;
    for (size_t i = 1; i < nCount; i++)
    {
        nMax = arrInt[i];
        j = i - 1;
        while (j >= 0 && arrInt[j] > nMax)
        {
            arrInt[j + 1] = arrInt[j];
            j--;
        }
        arrInt[j + 1] = nMax;
    }

    for (size_t i = 0; i < nCount; i++)
        printf("%d\n", arrInt[i]);