插入排序

一、定义

插入排序（Insertion Sorting）的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序。
具体步骤：

1. 将数组分为两部分，左侧已有序部分，右侧未排序部分；
2. 每次从右侧选择第一个数，从右到左依次与左侧的数比较，插入到左侧；

3. 如此往复，直到整个数组有序。

   
   1-1 插入排序运行轨迹

二、算法实现

public static void sort(Comparable[] a) {
    int n = a.length;
    for (int i = 0; i < n; i++) {
        for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
            exch(a, j, j - 1);
        }
        assert isSorted(a, 0, i);
    }
    assert isSorted(a);
}

三、性能分析

• 特点
  运行时间与输入有关，数组越有序，所需排序时间越短；
  最好的情况下（数组已有序），仅需比较N次，不需要移动；最坏情况下（数组完全逆序），需要移动至少(N²)/2次；
  插入排序对部分有序的数组十分高效，很适合小规模数组，同时也是很多高级排序算法的中间过程
• 时间复杂度
  O(N²)