102. 直接插入排序

基本思想

将序列中第一个元素作为有序序列，然后将剩下的n-1个元素按照关键字大小依次插入该有序序列，每插入一个元素后依然保持该序列有序，经过n-1趟排序后，成为有序序列。

解题之法

template <class T>
void InsertSort(T A[], int n){
    for (int i = 1; i < n; i++){
        int j = i;
        T temp = A[i];
        while (j > 0 && temp < A[j - 1]){
            A[j] = A[j - 1];
            j--;
}
        A[j] = temp;
}

}

复杂度

O(n*n) 稳定的