直接插入排序

思想

對於少量元素的排序，插入排序是一個有效的算法。它的工作方式像排序一手撲克牌。開始時，我們左手為空並且桌子上的牌面向下。然後，我們每次從桌子上拿走一張牌並將它插入到左手中正確的位置上。拿在左手上的牌總是排好序的，原來這些牌是桌子上牌堆中頂部的牌。

實現

假設輸入是 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;
     }
}