插入排序

1 .算法思想
 插入排序是最简单的排序算法之一。假定要将n个元素 a[0], a[1], · · · , a[n − 1] 按非降序排序，我们可以先来看一个小问题：将 a[0], a[1] 排序。由于a[0] 本身是有序的，那么只需要将 a[1] 插入a[0](即，若 a[1] ⩾ a[0]，则不进行操作;若a[1] < a[0]，则将a[0]与a[1] 交换)。接下来将a[2]插入到此前已经排好序的数组 a[0], a[1] 中;然后将a[3]插入到已经有序的数组 a[0], a[1], a[2] 中。以此类推。
  那么对于 a[i] = val, 我们则要将a[i]插入到已有序的数组a[0], a[1], a[2], ···, a[i − 1]中。
  首先将 val 与 a[i−1] 比较，若 val ⩾ a[i−1]，那么

    a[0], a[1], a[2], · · ·, a[i − 1], a[i]

已有序，停止。若val < a[i − 1]，则将a[i − 1]右移一个单位(即把 a[i − 1] 复制到a[1])，然后将val与a[i − 2]比较。若val ⩾ a[i − 2]，则由于此刻

    a[0], a[1], a[2], · · ·, a[i]

已排序，所以把val复制到a[i − 1]，停止。若val < a[i − 2]，则将a[i − 2]右移一个单位， 继续上述操作。

直到a[n] 插入到数组

    a[0], a[1], a[2], ···, a[n − 1]

中的正确位置，算法结束。

  由上易知，对于N的元素的插入排序，需要 N-1趟排序来完成。插入排序利用了这样一个事实：在对数组中p位置上的元素排序时，位置0到位置p-1的元素已经处于有序状态。

  下面以一个例子来说明，假定要排序的数组是

    36   14   27  40   31

那么我们需要4趟排序来完成：

• 第1趟，对14排序
  将14与36比较，由于14<36，故将36右移一个单元，14 插入第一个单元，结果为：

    14   36   27  40   31

• 第2趟，对27排序
  首先将27与36比较，27<36，故将 36 右移一个单位，再将27与14比较，27>14，故14不必移动，将27插入第二个单元，结果为：

    14   27   36  40   31

• 第3趟，对40排序
  由于40>36，故已经序，不需要移动，结果为：

    14   27   36  40   31

• 第4趟，对31排序
  由于 31<40，所以 40 右移一个单元，再将 31 和 36 比较，31<36，故 36 右移一个
  单元，接着和 27 比较，31>27，故 27 不必移动，31 插入第三个单元。结果为：

    14   27   31  36   40

这样就把插入排序完成了。

2.算法实现

import java.util.Arrays;

/**
 * @Author: 落脚丶
 * @Date: 2017/10/17
 * @Time: 下午3:44
 * @ClassName: InsertionSort
 * @Description: 插入排序
 */
public class InsertionSort {
    public static void main(String[] args) {
        int [] test = new int[]{36,14,27,40,31};
        insertionSort(test);
        System.out.println(Arrays.toString(test));
    }
    public static void insertionSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int j = i;
            int val = a[i]; // 从第二个元素开始排
            while (j > 0 && val < a[j-1]) {
                a[j] = a[j-1];
                j--;
            }
            a[j] = val;
        }
    }
}

3.算法复杂度分析
  插入排序在最坏的情况，对于a[i]总要插入到a[0]位置，这是while循环的次数最多。 当输入以降序排列时就会出现这种状况。在这种情况下，i = 1需要执行 1 次while循环，i = 2需要2次，· · · ，i = n − 1需要执行n − 1次，故while循环体之行的总次数为:

    1+2+3+···+(n−1) = O(n²)

  最好的情况，输入已经是有序的序列，while 只是进行判断而不执行。故时间复杂度 为：O(n)。

  平均情况，有一个定理：通过交换相邻元素进行排序的任何算法平均时间都需要 Ω(n²) 时间。

故插入排序的平均时间复杂度为 O(n²)。