1.思想：每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。
2.空间效率：空间复杂度为O(1)
时间效率：
适用性：顺序存储和链系存储
稳定性： 稳定性
3.java代码：
/**

• @插入排序

• @author zx

• @date 2020-06-27
  */
  public class InsertSort {
  private int[] array;
  private int length;

  public InsertSort(int[] array){
  this.array = array;
  this.length = array.length;
  }

  public void display(){
  for(int a: array){
  System.out.print(a+" ");
  }
  System.out.println();
  }

  /*
  * 插入排序方法
  */
  public void doInsertSort(){
  int k=0,c=0;
  for(int index = 1; index<length; index++){//外层向右的index，即作为比较对象的数据的index
  System.out.println(“执行次数：”+(++k));
  int temp = array[index];//用作比较的数据
  int leftindex = index-1;
  while(leftindex>=0 && array[leftindex]>temp){//当比到最左边或者遇到比temp小的数据时，结束循环
  System.out.println(“比较次数：”+(++c));
  array[leftindex+1] = array[leftindex];
  leftindex–;
  }
  array[leftindex+1] = temp;//把temp放到空位上
  }
  }

  public static void main(String[] args){
  int[] array = {38,65,97,76,13,27,49};
  InsertSort is = new InsertSort(array);
  System.out.print(“排序前的数据为：”);
  is.display();
  is.doInsertSort();
  System.out.print(“排序后的数据为：”);
  is.display();
  }
  4.结果：
  排序前的数据为：38 65 97 76 13 27 49
  排序后的数据为：13 27 38 49 65 76 97