插入排序（Insertion Sort)的基本思想：每次将一个带排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。

类似扑克牌摸牌：摸来的第一张牌无须整理，此后每次从卓上的牌（无序区）中模最上面的1张并插入手牌（有序区）中正确位置上。为了找到这个位置，须从左向右（或从右向左）将摸来的牌与手牌逐一比较。

void insertionSort(int[] A,int n){
    if(A == null || n <= 1){
        return;
    }
    int i,j,temp;

    for(i = 1;i < n; i++){
        temp = A[i];
        for(j = i;j > 0 && temp < A[j-1];j--){
            A[j] = A[j - 1];
        }
        A[j] = temp;
    }
}

算法分析：

• 时间复杂度：正序O（n） 逆序和无序O（n2）；

• 空间复杂度：就地排序，O（1）；

• 稳定排序算法