直接插入排序

算法思想：将待排序表分为两部分，左边为有序区，右边为无序区。将无序区的元素与有序区的每一个元素比较，小于的话，将该元素插进有序区相应的位置中。

代码描述：

    /**
     * 插入排序
     * @param args
     */
    public void Sort(int A[]){
        int j;
        for(int i=2;i<A.length;i++){
            A[0]=A[i];           //设置监视哨
            j=i;
            while(A[j-1]>A[0]){ //在已将排好序的区域中插入
                A[j]=A[j-1];    //交换元素的大小，大的排在后面
                j--;
            }
            A[j]=A[0];          //插入元素
        }
        for(int i=1;i<A.length;i++)
            System.out.print(A[i]+" ");
    }

稳定性:稳定
空间性能：1个辅助空间（需要一个监视哨的空间来辅助）
时间性能：O（n^2）

H_JJia.png

关于排序算法稳定性:

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的