## 直接插入排序（Direct Insertion Sort）

插入排序的设计初衷是**往有序的数组中快速插入一个新的元素**。它的算法思想是：把要排序的数组分为了两个部分, 一部分是数组的全部元素(除去待插入的元素), 另一部分是待插入的元素; 先将第一部分排序完成, 然后再插入这个元素. 其中第一部分的排序也是通过再次拆分为两部分来进行的.

插入排序由于操作不尽相同, 可分为 `直接插入排序` , `折半插入排序`(又称二分插入排序), `链表插入排序` , `希尔排序` 。我们先来看下直接插入排序。

- 基本思想

  直接插入排序的基本思想是：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过为止。

  ![insertion.gif](https://i.loli.net/2017/10/20/59e9efbeea1fb.gif)

- 算法描述

  一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

  如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找插入排序。

- 代码实现

  ```java
  /**
   * 插入排序
   * <p>
   * 1. 从第一个元素开始，该元素可以认为已经被排序
   * 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
   * 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
   * 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
   * 5. 将新元素插入到该位置后
   * 6. 重复步骤2~5
   *
   * @param arr 待排序数组
   */
  public static void DirectInsertionSort(int[] arr) {
      for (int i = 0; i < arr.length - 1; i++) {
          for (int j = i + 1; j > 0; j--) {
              if (arr[j - 1] <= arr[j]) {
                  break;
              }
              int temp = arr[j];  //交换操作
              arr[j] = arr[j - 1];
              arr[j - 1] = temp;
              System.out.println("Sorting: " + Arrays.toString(arr));
          }
      }
  }
  ```

- 小结

  直接插入排序复杂度如下：

  | 平均时间复杂度 | 最好情况 | 最坏情况  | 空间复杂度 |
  | ------- | ---- | ----- | ----- |
  | O(n²)   | O(n) | O(n²) | O(1)  |

  文件初态不同时，直接插入排序所耗费的时间有很大差异。若文件初态为正序，则每个待插入的记录只需要比较一次就能够找到合适的位置插入，故算法的时间复杂度为O(n)，这时最好的情况。若初态为反序，则第i个待插入记录需要比较i+1次才能找到合适位置插入，故时间复杂度为O(n2)，这时最坏的情况。

  > 注意： 由于直接插入排序每次只移动一个元素的位，并不会改变值相同的元素之间的排序， 因此它是一种稳定排序。