数据结构与算法——选择排序和插入排序

1. 回顾

前面说到了冒泡排序，这是一种时间复杂度为 O(n²) 、是原地排序和稳定的的排序算法，具体思路是：根据相邻两个元素之间比较大小，然后交换位置，得出最后排序的结果。具体可参考我写的这一篇文章：数据结构与算法——冒泡排序，今天来看看另外两种基础的排序算法：选择排序和插入排序。

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(n²)，并且没有借助额外的存储空间，是一种原地排序算法。那么选择排序是稳定的吗？答案是否定的，举个例子：排序的数组为 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(n²)。

最后还有个问题，为什么在实际中，插入排序的比冒泡排序使用的更加广泛呢？虽然这两个排序算法的平均时间复杂度都是 O(n²)，但是结合代码，不难发现，它们涉及到的数据交换操作时略有差别的。

冒泡排序在交换数据的时候，需要进行三次赋值操作，而插入排序只需要一次。

//插入排序的赋值操作            
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;
    }

在数据规模小的时候，这样的差别没什么影响，但是如果我们要排序的是一组较大的数据，那么两种排序算法的执行时间的差别就会很明显了。