数据结构与算法——选择排序和插入排序
1. 回顾
前面说到了冒泡排序，这是一种时间复杂度为 O(n2) 、是原地排序和稳定的的排序算法，具体思路是：根据相邻两个元素之间比较大小，然后交换位置，得出最后排序的结果。具体可参考我写的这一篇文章：数据结构与算法——冒泡排序，今天来看看另外两种基础的排序算法：选择排序和插入排序。
2. 选择排序
先来看看选择排序，选择排序的思路其实很简单，将排序的数据分为已排序区间和未排序区间，一般是以第一个元素为已排序区间，然后依次遍历未排序区间，找到其最小值，和未排序区间的最后一个值进行比较，交换位置。未排序区间遍历完毕，则排序结束。光说可能有点抽象，我画了一张图来帮助你理解：
是不是很简单呢？下面是它的代码实现：
public class SelectionSort {
public static void selectionSort(int[] data){
int length = data.length;
//如果只有一个元素，或者数组为空，则直接退出
if (length <= 1) return;
for (int i = 0; i < length - 1; i++) {
int min = i + 1;
//找到最小值
for (int j = i + 1; j < length; j++) {
if (data[j] < data[min]) min = j;
}
//交换位置
if (data[min] < data[i]){
int temp = data[min];
data[min] = data[i];
data[i] = temp;
}
}
}
}结合代码分析，选择排序在最好、最坏和平均情况下的时间复杂度都是 O(n2)，并且没有借助额外的存储空间，是一种原地排序算法。那么选择排序是稳定的吗？答案是否定的，举个例子：排序的数组为 data[2, 2, 1, 3, 5, 4, 8]，第一次遍历未排序的数组，找到最小值为 1，和第一个 2 交换位置，那么这两个 2 的前后顺序就被打乱了，所以稳定性被破坏。正因如此，选择排序比起冒泡排序和插入排序就显得逊色很多了。
3. 插入排序
我们再来看看插入排序，其实思路和上面的选择排序非常的类似，也是将排序数据分为已排序区间和未排序区间，依次遍历未排序区间，和已排序区间的值进行比较，将其插入到合适的位置上，直至将未排序的区间数据遍历完。
你可以结合下面的图来理解：
可以看到，和选择排序一样，将第一个数据作为已排序区间，第一次遍历到 2 ，将其插入到 4 后面，然后再依次遍历。
下面是代码实现：
public class InsertionSort {
public static void insertionSort(int[] data){
int length = data.length;
if (length <= 1) return;
for (int i = 1; i < length; i++) {
int value = data[i];
int j = i - 1;
for (; j >= 0; j --){
if (data[j] > value) data[j + 1] = data[j];
else break;
}
data[j + 1] = value;
}
}
}很显然，插入排序也是稳定的，因为我们是在 data[j] > da[j + 1] 的时候，才进行数据交换，不会影响到相同元素的前后位置。并且，插入排序是原地排序，最好情况下，数组本来就是有序的，所以我们只需要遍历一次数组就可以了，时间复杂度是 O(n)，最坏情况和平均情况下，时间复杂度都是 O(n2)。
最后还有个问题，为什么在实际中，插入排序的比冒泡排序使用的更加广泛呢？虽然这两个排序算法的平均时间复杂度都是 O(n2)，但是结合代码，不难发现，它们涉及到的数据交换操作时略有差别的。
冒泡排序在交换数据的时候，需要进行三次赋值操作，而插入排序只需要一次。
//插入排序的赋值操作
for (; j >= 0; j --){
if (data[j] > value) data[j + 1] = data[j];
else break;
}
//冒泡排序的赋值操作
for (int j = 0; j < n - i - 1; j++) {
//如果data[j] > data[j + 1]，交换两个数据的位置
if (data[j] > data[j + 1]){
int temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}在数据规模小的时候，这样的差别没什么影响，但是如果我们要排序的是一组较大的数据，那么两种排序算法的执行时间的差别就会很明显了。