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(n2)
最好的情况，输入已经是有序的序列，while 只是进行判断而不执行。故时间复杂度 为：O(n)。
平均情况，有一个定理：通过交换相邻元素进行排序的任何算法平均时间都需要 Ω(n2) 时间。
故插入排序的平均时间复杂度为 O(n2)。
