排序之插入排序

插入排序或者叫直接插入排序，简单粗暴，核心思想就是：不管选最大还是最小，每次都把没有排序的元素插入到已经排序的元素中间的合适的位置上。所以直接插入排序是把为排序的元素与排好序的元素逐一对比，直到处于排好序的元素中间。

直接插入排序是稳定排序，时间复杂度为：。

图示：

C++代码实现：

int insertSort(int *pArray, int len)    
{
    if (NULL == pArray || len < 1)
    {
        return 0;
    }
    for (int i = 1; i < len; i++)
    {
        if (pArray[i] < pArray[i - 1])
        {
            int tmp = pArray[i];
            int j = i - 1;
            while (pArray[j] > tmp)
            {
                pArray[j + 1] = pArray[j];
                j--;
            }
            pArray[j + 1] = tmp;
        }
    }
    return 1;
}

江送巴南水，山横塞北云。
津亭秋月夜，谁见泣离群。
乱烟笼碧砌，飞月向南端。
寂寞离亭掩，江山此夜寒。

  -- 王勃 《江亭夜月送别二首》