直接插入排序是最简单的排序方法，它的基本操作是将一个记录插入到以排序好的有序表中，从而得到一个新的记录数增一的有序表。

* 空间复杂度O(1)

* 时间复杂度O(n²)

void InsertSort(int A[], int n){
    int i,j,temp; //定义变量
    for(i=1; i<n; i++){
        if(A[i]<A[i-1]){
            temp=A[i]; //临时存储
            for(j-i-1;j>=0 && A[j]>temp; --j)
                A[j+1]=A[j];
            A[j+1]=temp;
        }
    }
}

void InsertSort(int A[], int n){
    int i,j;
    for(i=2; i<=n; i++){
        if(A[i]<A[i-1]){
            A[0] = A[i]; //游标记录
            for(j=i-1; A[0]<A[j]; --j)
                A[j+1] = A[j];
            A[j+1] = A[0];
        }
    }
}