思路：

对某一个元素，假设该元素前面都已经有序，元素后面元素都无序。

找到恰小于等于该元素的位置后插入该元素，同时此时该元素位置到之前该元素之间的元素位置都后移。

空间复杂度：O(1)

时间复杂度：O(n²)

是稳定的排序方法

#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <string.h> 
#include <algorithm>
using namespace std;
int A[1000]={0,49,38,65,97,76,13,27,49,55,4};
void InsertSort(int n){//n为数组大小 (从小到大)
    int i,j;
    for(i=2;i<=n;i++){//      假定i之前的数据已经排好序 
        if(A[i]<A[i-1]){//    后一项比前一项小，则需要交换 
            A[0]=A[i];         //记录当前元素到A0 
            for(j=i-1;A[0]<A[j];j--){          //把当前元素插入到恰好小于等于该元素后 
                A[j+1]=A[j];                   //从后往前移动 
            }
            A[j+1]=A[0];                       // 恰好小于等于该元素后插入该元素 
        }
    }
} 
int main(){
    InsertSort(10);
    for(int i=1;i<=10;i++){
        cout<<A[i]<<" ";
    }
    return 0;
}