排序(上)：为什么插入排序比冒泡排序更受欢迎？（插入排序与选择排
排序(上)：为什么插入排序比冒泡排序更受欢迎？（插入排序与选择排序）
一、插入排序
首先来看一个问题，一个有序的数组，我们往里面添加一个新的数据后，如何继续保持数据有序呢？很简单，我们只要遍历数组，找到数据应该插入的位置，将其插入即可。
image
这是一个动态排序的过程，即动态的往有序集合中添加数据，我们可以通过这种方法保持集合中的数据一致有序。而对于一组静态数据，我们也可以借鉴上面讲的插入方法，来进行排序，于是就有了 插入排序算法。
插入排序具体是如何借助上面的思想来实现排序的呢？
首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
现有数据 [4,5,6,1,3,2]，下图中，左侧为已排序区间，右侧是未排序区间。
image
插入排序也包含两种操作，一种是元素的比较，一种是元素的移动。当我们需要将一个数据 a 插入到已排序区间时，需要拿 a 与已排序区间的元素依次比较大小，找到合适的插入位置。找到插入点之后，我们还需要将插入点之后的元素顺序后移一位，这样才能腾出位置给元素 a 插入。
对于不同的查找插入点方法（从头到尾、从尾到头），元素的比较次数是有区别的。但对于一个给定的初始序列，移动操作的次数总是固定的，就等于逆序度。（就是不管如何优化查找插入点的算法，对于一个已知序列，我们总要移动同样的次数来给要插入的数据腾出位置）
为什么说移动次数就等于逆序度呢？看下面的图就明白了。
满有序度是：n(n-1)/2 = 15，初始序列的有序度是 5，所以逆序度是 10。
image
插入排序的代码：
// 插入排序，a 表示数组，n 表示数组大小
public void insertionSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 1; i < n; ++i) {
int value = a[I];
//注意这里，j是定义在内循环外面的
//所以可以在外循环结束前，对a[j+1] 赋值
//每次内循环结束时，若数据一直在移动，那么 j 的一定为 -1
//若出现了 break，说明不需要数据移动，a[j]及其前面的数据都是有序并且不大于 a[i] 及其后面的数据
//若 j 的值发生了变化，则将数据插入在 j+1 位置
//若 j 的值没发生变化，则将数据插入在 j+1 位置（正好就是i，也就是没变）
int j = i - 1;
// 查找插入的位置
for (; j >= 0; --j) {
if (a[j] > value) {
//每个内循环第一次执行的时候，a[j+1] 其实就是 a[i]
//此处是在进行数据移动
a[j+1] = a[j];
} else {
break;
}
}
a[j+1] = value; // 插入数据
}
}
此处有三个问题：
第一，插入排序是原地排序算法吗？
是，插入排序的运行并不需要额外的内存空间，所用内存空间是常量级的，所以插入排序是原地排序算法，空间复杂度为 ○(1)
第二，插入排序是稳定的排序算法吗？
上述代码中，我们将后面出现的相同元素，插入到前面出现的相同元素的后面，这样就可以保持原有的前后数据不变，所以插入排序是稳定的排序算法。
image
第三，插入排序的时间复杂度是多少？
最好情况：如果待排序数据，已经是有序的了，那么每次执行内循环的if语句时，都不成立，也就是每次刚执行第一次内循环的时候，就会走到 break，那么也就是外循环每执行一次，内循环也只会执行一次（那么内循环实际上就与 循环变量 无关了，只是一个常量时间的操作），所以此时时间复杂度为 ○(n) （外循环与 循环变量 有关）。
最坏情况：如果待排序数据，是倒序的，那么每次执行内循环的时候，内循环都会执行 最大次数，此时就是嵌套的双层循环了，那么时间复杂度就为 ○(n²)。
在学习数组的时候学习到，在数组中随机位置插入一个数据的平均时间复杂度是 ○(n)。所以对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行 n 次插入操作，所以平均时间复杂度为 ○(n²)
二、选择排序
选择排序算法的实现思路有点类似插入排序，也分为已排序区间和未排序区间。但是选择排序 每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
image
public static void selectSort(int[] a,int n){
if(n <= 1){
return;
}
for (int i = 0; i < n; i++) {
int min = a[I];
for (int j = i; j < n; j++) {
if(a[j] < min){
int temp = a[j];
a[j] = min;
min = temp;
}
}
a[i] = min;
}
}
继续思考三个问题：
第一，选择排序是原地排序算法吗？
是
第二，选择排序是稳定排序算法吗？
不是，因为选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交互位置，这样破坏了稳定性
第三，时间复杂度
最好情况、最坏情况、平均情况都是 ○(n²)，因为一定会执行双层嵌套for循环
image
三、解答开篇
冒泡排序和插入排序的时间复杂度都是 ○(n²)，都是原地排序算法，都是稳定排序算法，为什么插入排序要比冒泡排序受欢迎呢？
前面提到过，冒泡排序不管怎么优化，元素交换的次数是一个固定值，我们称它为逆序度。插入排序同样的，不管怎么优化，元素移动的次数也是一个固定值，也就是原始数据的逆序度。
但是，从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动复杂，冒泡排序需要三个赋值操作，而插入排序只需要一个。
冒泡排序中数据的交换操作：
if (a[j] > a[j+1]) { // 交换
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true;
}
插入排序中数据的移动操作：
if (a[j] > value) {
a[j+1] = a[j]; // 数据移动
} else {
break;
}
我们把执行一个赋值语句的时间粗略地计为单位时间（也就是常量时间）（unit_time），然后分别用冒泡排序和插入排序对同一个逆序度是 k 的数组进行排序，用冒泡排序，需要 k 次交换操作，每次需要 3 个赋值语句，所以交换操作总耗时为 3*k 单位时间。而插入排序中数据移动操作只需要 k 个单位时间。
所以，虽然冒泡排序和插入排序在时间复杂度上是一样的，都是 ○(n²)，但是如果我们希望把性能优化做到机制，那肯定首选插入排序。插入排序的算法思路也有很大的优化空间，这篇只是最基础的一种。
插入排序的优化：希尔排序。
四、课后思考
特定算法是依赖特定的数据结构的。我们今天讲的几种排序算法，都是基于数组实现的，如果数据存储在链表中，这三种排序算法还能工作吗？如果能，那相应的时间、空间复杂度由是多少呢？
