基本思想
将序列中第一个元素作为有序序列，然后将剩下的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) 稳定的
