把所有需要排序的数据分成两个集合，一个是待排序集合，一个是已排序的集合，算法每次从未排序集合顺序或随机拿取一个数据，把它加入到已排序集合使其有序，直到未排序集合中的数据被取走完，算法结束

public class Test6{
  public static void main(String args[]){
    int a[]=new int[]{4,5,8,7,4,1,2,3,6,5,56};
    for(int i=1;i<a.length;i++){
      int j=i-1,temp=a[i];
      while(j>0&&a[j]>temp){
        a[j+1]=a[j--];
      }
      a[j+1]=temp;
    }
    for(int i=1;i<a.length;i++){
      System.out.print(a[i]+" ");
    }
  }
}

平均时间复杂度：O(n²)

平均空间复杂度：O(1)