直接插入排序

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

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

• 基本思想

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

  

• 算法描述

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

  1. 从第一个元素开始，该元素可以认为已经被排序

  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描

  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置

  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

  5. 将新元素插入到该位置后

  6. 重复步骤2~5

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

• 代码实现

  /**
   * 插入排序
   * <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)，这时最坏的情况。

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