//参数：数组和数组长度
//注意：0-j-1是已经排序的,要插入第j个元素,0-j-1依次向后挪动一位直至j找到应该放的位置
//算法时间复杂度：o(n的平方）；空间复杂度:O(1)

//应用：大部分已排序

void Insert_Sort(int A[],int n)
{
　　int i,j;
　　int key;
　　for(j=1;j<n;j++)
　　{
　　　　key=A[j];
　　　　i=j-1;
　　　　while(A[i]>key)
　　　　{
　　　　　　A[i+1]=A[i];
　　　　　　i=i-1;
　　　　}
　　　　A[i+1]=key;
　　　}
}

插入排序