插入排序：将记录插入到已经排好序的有序链表中，从而得到一个新的记录增1的有序表
最优时间复杂度 O(n), 最坏时间复杂度 O(n2)

  1. /**
  2.  * @Description: 插入排序：将记录插入到已经排好序的有序链表中，从而得到一个新的记录增1的有序表
  3.  * 最优时间复杂度 O(n), 最坏时间复杂度 O(n2)
  4.  * @Author: lizhouwei
  5.  * @CreateDate: 2018/6/23 9:52
  6.  * @Modified By:
  7.  */
  8. public class InsertSort {
  10.     public static void insertSort(Integer[] arr) {
  11.         if (arr == null || arr.length == 0) {
  12.             return;
  13.         }
  14.         SortUtil.printArray("插入排序前", arr);
  15.         Integer temp = 0;
  16.         int j = 0;
  17.         for (int i = 1; i < arr.length; i++) {
  18.             if (arr[i] > arr[i - 1]) {
  19.                 continue;
  20.             }
  21.             temp = arr[i];
  22.             for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
  23.                 arr[j + 1] = arr[j];
  24.             }
  25.             arr[j + 1] = temp;
  26.         }
  28.         SortUtil.printArray("插入排序后", arr);
  30.     }
  31. }

复杂度分析

时间复杂度：
当最好的情况，也就是要排序的表本身就是有序的，那么每次需要进行需要n-1次比较，总共需要比较插入排序 - 图1次，没有数据交换，时间复杂度为插入排序 - 图2。
当最坏的情况，即要排序的表是逆序情况，此时需要比较
插入排序 - 图3次，因此时间复杂度为 插入排序 - 图4；