类似扑克牌思想，默认array[0]为第一张扑克牌，并且第一个循环从1开始，每次拿一张扑克牌和手里的牌做比较，然后插入响应的位置

算法步骤

  1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
  2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

image.png

  1. public static int[] insetSort(int[] sourceArray){
  2.         int[] arr = Arrays.copyOf(sourceArray,sourceArray.length);
  3.         for(int i =1;i<arr.length;i++){
  4.             int tmp = arr[i];
  5.             int j = i;
  6.             while (j>0&&tmp<arr[j-1]){
  7.                 arr[j] = arr[j-1];
  8.                 j--;
  9.             }
  10.             if (j!=i){
  11.                 arr[j] = tmp;
  12.             }
  13.         }
  14.         return arr;
  15.     }

或者是

  1. private int[] insertionSort(int[] arrays) {
  2.         for (int i = 1; i < arrays.length; i++) {
  3.             int value = arrays[i];
  4.             int j = i - 1;
  5.             for (; j >= 0; --j) {
  6.                 if (value < arrays[j]) {
  7.                     arrays[j + 1] = arrays[j];
  8.                 } else {
  9.                     break;
  10.                 }
  11.             }
  12.             arrays[j + 1] = value;
  13.             System.out.print("第" + i + "次交换");
  14.             printAll(arrays);
  15.         }
  16.         return arrays;
  17.     }

go 实现

  1. // 插入排序
  2. func InsertionSort(a []int){
  3.       for i:=1;i<len(a);i++{
  4.           v := a[i]
  5.           j :=i-1
  6.           // 当前已经排好的队列
  7.           for ;j>=0;j--{
  8.             if a[j]>v {
  9.                 a[j+1]=a[j]// 移动数据
  10.             }else {
  11.                 break
  12.             }
  13.         }
  14.         a[j+1]= v
  15.       }
  16. }