插入排序

插入排序也是 插入排序 - 图1 时间复杂度的排序算法。

排序流程

插入排序的思想，进行两次循环遍历。在内嵌循环遍历中，选择一个元素，与之前的元素做比较。如果当前元素比前一个元素小，说明需要交换位置。如果当前元素比前一个元素大，再往前比较也就没什么意思了，直接跳出嵌套循环，进入下一个的外层循环。
插入排序与选择排序有有些相似，都进行了两次遍历，但是插入排序发现当前元素比前一个元素大，就直接跳出嵌套循环，比选择排序性能稍微会好一点。
在内嵌循环中，插入排序是从后往前进行遍历，而冒泡排序是从前向后进行遍历。
插入排序流程图如下：
插入排序 - 图2

排序代码

  1.     private static void insertSort(int[] arr) {
  2.         if (Objects.isNull(arr)) {
  3.             return;
  4.         }
  5.         int length = arr.length;
  6.         if (arr.length <= 1) {
  7.             return;
  8.         }
  9.         int end = length - 1;
  10.         // 因为内层循环会从i开始，与i-1索引对应的值做比较，而i-1始终>=0，所以i的取值范围是(0,end]
  11.         for (int i = 1; i <= end; i++) {
  12.             // 从后往前遍历
  13.             for (int j = i; j > 0; j--) {
  14.                 // 如果左侧索引的值大于右侧索引的值，说明该把左侧索引的值往右边挪
  15.                 // 因为数组左边的值小于右边的值才表示是升序
  16.                 if (arr[j - 1] > arr[j]) {
  17.                     swap(arr, j, j - 1);
  18.                 } else {
  19.                     break;
  20.                 }
  21.             }
  22.         }
  23.     }
  25.     private static void swap(int[] arr, int i, int j) {
  26.         int temp = arr[i];
  27.         arr[i] = arr[j];
  28.         arr[j] = temp;
  29.     }