将待排序列看做左右两个子序列,左子序列有序。则一趟直接插入的排序过程为:对于右侧序列的第一个记录,在左侧有序序列中找到一个合适的位置,插入。从后向前查找合适的位置,同时向后移动记录。

代码如下:

/* 直接插入排序 */
void StraightInsertionSort(int a[], int n)
{
    int i, j, k, tmp;
    for (i=1; i<n; i++) // 假定a[0]有序
    {
        tmp = a[i]; // 待排记录
        // 从后向前查找插入位置,同时将已排序记录向后移动
        j = i - 1;
        while (j > -1 && tmp < a[j])
        {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = tmp;   // 将待排记录放到合适位置
    }
}

直接插入排序的时间复杂度为O(n2),空间复杂度为O(1)。