插入排序——O(n^2)

时间复杂度

原理图：

public class Insertion_sort {
    public static void main(String[] args) {
        int[] A={5,2,4,6,1,3};
        for(int j=1;j<A.length;j++){
            int key=A[j];//key为正在插入的数据
            int i=j-1;
            while (i>=0&&A[i]>key){
                A[i+1]=A[i];//实现每一位都后移，直到A[i]<=key
                i=i-1;//i--
            }
            A[i+1]=key;//赋值
        }
        for(int i=0;i<A.length;i++){
            System.out.println(A[i]);
        }
    }
}