直接插入排序

直接插入排序

思想

对于少量元素的排序，插入排序是一个有效的算法。它的工作方式像排序一手扑克牌。开始时，我们左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入到左手中正确的位置上。拿在左手上的牌总是排好序的，原来这些牌是桌子上牌堆中顶部的牌。

实现

假设输入是 n 个数的一个序列a[0...n-1]，则实现代码如下

/**
*  @description 插入排序
*  @param    int a[]，待排序数组*  @param    int n，数组a的元素个数
*  @return 无返回值
*/
void InsertionSort(int a[], int n)
{
    int i, j, key;
 
    for (i = 1; i < n; ++i)
    {
        key = a[i];                    //临时保存a[i]
 
        //插入a[i]到已排好序的a[0...i-1]
        for (j = i - 1; j >= 0 && a[j] > key; --j)
            a[j + 1] = a[j];           //大于a[i]的值往后移动，留出空位待a[i]插入
        a[j + 1] = key;
     }
}

本文永久更新链接地址：