插入排序

插入排序主要思想：从第二个元素开始，向前插入在合适的位置。平均复杂度O(n)。

template<typename T>
void insertSort(T* a, int length)
{
    for (int i = 1; i < length; i++)
    {
        int j = i;
        T temp = a[j];//记录当前待排序的元素，使这个位置变为“空
        while (j > 0 &&  temp < a[j-1])//与前一位比较
        {
            a[j] = a[j -1];//后移
            j--;//前移
        }
        a[j] = temp;//插入
    }
}