【算法】排序（四）归并排序
上次给大家说了说简单的冒泡排序，这次我们来说一说插入排序
插入排序的做法就像是我们日常生活中玩扑克牌一样，每次抽一张牌，将扑克牌按一定顺序插入手牌中，一步步完成排序
本文将介绍以下内容
排序思想
算法实现（JAVA）
测试阶段
排序过程讲解
算法分析
排序思想
插入排序同样有内循环和外循环，外循环执行n – 1次，内循环负责比较相邻两个数的大小并交换（如果需要）。每次将未排序序列里的第一个数与后一个数比较，如果后者小，就交换二者的位置，并和以排序的序列元素依次比较并交换（如果需要）。
就如同玩扑克牌，每次抽取的一张牌都要与所有手牌一对一比较，并确定最终插入的位置。
算法实现
1. 外循环
public static void insertionSort(int[] a) {
int n = a.length;
for (int i = 1; i < n; i++) {
}
}循环次数为n – 1，否则数组下标越界，下文会说明原因。
2. 内循环
for (int j = i; j > 0 && a[j] < a[j - 1] ; j--) {
int temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
}交换条件为后一项小于前一项，每次都是a[j]与a[j – 1] 比较，所以只能有n – 1 次循环，否则数组下标越界。
所以，插入排序的代码块就是如此了：
public static void insertionSort(int[] a) {
int n = a.length;
for (int i = 1; i < n; i++) {
for (int j = i; j > 0 && a[j] < a[j - 1] ; j--) {
int temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
}
}
}测试阶段
我们还是用十个随机数字来作为输入：
public static void main(String[] args){
int[] a = new int[10];
for (int i = 0; i < a.length; i++) {
a[i] = (int)(Math.random()*100);
System.out.print(a[i] + " ");
}
System.out.println();
insertionSort(a);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}随机选取几组结果：
排序过程讲解
我们以result_1的排序结果作为示例来解释一下排序过程：
-
第一步：74与11比较，交换顺序，已排序序列为[11,74]
-
第二步：74与99比较，不交换顺序，已排序序列为[11,74,99]
-
第三步：99与85比较，交换顺序，85与74比较，不交换顺序，已排序序列为[11,74,85,99]
-
第四步：99与14比较，交换顺序，85与14比较，交换顺序，74与14比较，交换顺序，已排序序列为[11,14,74,85,99]
-
第五步：99与74比较，交换顺序，85与74比较，交换顺序，74与74比较，不交换顺序，已排序序列为[11,14,74,74,85,99]
-
第六步：99与24比较，交换顺序，85与24比较，交换顺序，74与24比较，交换顺序，74与24比较，交换顺序，14与24比较，不交换顺序，已排序序列为[11,14,24,74,74,85,99]
-
第七步：99与90比较，交换顺序，85与90比较，不交换顺序，已排序序列为[11,14,24,74,74,85,90,99]
-
第八步：99与比54较，交换顺序，85与54比较，交换顺序，74与53比较，交换顺序，74与54比较，交换顺序，24与54比较，不交换顺序，已排序序列为[11,14,24,54,74,74,85,99]
-
第九步：99与82比较，交换顺序，85与82比较，交换顺序，
74与82比较，不交换顺序，已排序序列为[11,14,24,74,74,85,90,99]
n个元素的数组，经历n – 1次排序，总而言之，如果两元素比较，后者较小，就有可能多次比较，最后插入较前的位置。
算法分析
1. 特点
- 插入排序对于较为有序（部分有序）的数组时极为高效，因为有序的两个数不满足内循环的循环条件，所以可以直接跳过，极大增加效率。
2. 时间复杂度
-
最优情况：数组全部按升序排列，只需要进行n – 1次的比较就可完成，不需要交换
-
最差情况：数组全部按降序排列，需要进行n(n – 1) / 2次比较
(1 + 2 + 3 + … + n – 1) = n(n – 1) / 2，需要进行n(n – 1) / 2次交换 -
正常来说，插入排序的时间复杂度为O(n2)
3. 空间复杂度
插入排序需要一个临时变量来交换元素，所以空间复杂度为O(1)
4. 稳定性
插入排序是稳定的，例如result_1中，排序前a[0] = a[5] = 74，且a[0]代表的74在a[5]代表的74之前。在排序过程中，两个74相遇，并没有交换位置，所以插入排序是稳定的
插入排序就讲到这，下一篇文章将会是归并排序。