[数据结构与算法]插入排序——直接插入排序

【基本思想】：顺序的把待排序的数据元素按其关键字的大小插入到已排序数据元素的适当位置。自己和数据元素个数从只有一个数据元素开始，逐次增大，当子集合大小最终和集合大小相同时，排序结束。

插入排序的理解关键在于理解下面三个问题：

? ? ? ? 1.往哪里进行插入

? ? ? ? 2.把哪个值进行插入

? ? ? ? 3.怎么实现插入的

答：通过for循环从0到n-1进行遍历，前i为是排好序的，所以要进行的是将第i+1位与前i进行对比查找插入位置，在比较的时候，把前面的逐个后移，第i位覆盖第i+1位，第i-1位覆盖第i位以此类推。

void InsertSort(DataType a[],int n)
{
    int i,j;
    DataType temp;

    for(i = 0;i < n-1;i++)
    {
        temp = a[i+1];//定位第i+1位的数据，用于查找位置后的交换，避免移位时被覆盖

        j = i;  //用于第i+1位与前i位进行对比时的下标递减遍历。
        while(j > -1 && temp.key < a[j].key)
        {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = temp;
    }
}

红色为每次排序后前i位已排序区域，紫色位将要插入的数值

不难看出来，其最好的情况下的时间复杂度位O（n);最坏的情况下位O(n^2);