算法基础 - 排序(二)

前言

在上一篇博文中，我们为研究排序算法做了基本的准备工作，并且讲到了两种排序算法，那么在这篇文章中，会讲到接下来的几种排序算法，它们分别是：选择排序、归并排序

选择排序

稳定性：否

时间复杂度： $O(n^2)$ （平均）

选择排序是一种十分简单的排序方式，它每次找出乱序集合中最小的值，并将其与集合中最前端的值进行交换，最终完成其排序的过程．

我们将每一步操作归纳为以下步骤，在此之前，我们选定i = 0作为乱序集合的初始起点：

遍历起点索引及其之后的所有元素，找到其中最小值的索引位置
将最小值与起点元素交换位置
将选定起点后移一位
重复进行上述过程

我们认为，每次选定的起点索引位置之后的子集合是乱序的，当每次选出最小值并与集合顶端元素交换后，显然前i + 1项元素是有序的，因此无需对此前元素进行任何操作．

在遍历至集合末尾后，即进行至多n (n = list.size - 1)次操作后，可以认为当前整个集合是有序的．

在选择排序中，一个重要的步骤是交换操作，也是由于交换操作，导致了选择排序并不是一种稳定的排序算法，这是由于每次交换两个元素的位置后，相等元素的相对位置也可能会发生改变．

假如给定一个乱序序列[5(a), 3, 5(b), 2]，在排序过程中，我们将元素2同元素5(a)进行了交换,导致5(a)与5(b)的顺序发生了变化，这种顺序的改变，导致了选择排序的不稳定，值得注意的是，在一些场景下使用不稳定的排序算法会严重影响结果，应当谨慎选择．

下面给出该算法的实现：

public static ArrayList selectSort(ArrayList nums) {
        for (int i = 0; i < nums.size(); i++) {
            //选中的值
            int value = i;
            //求取最小值位置索引
            for (int j = i + 1; j < nums.size(); j++) {
                //更新较小值位置索引
                value = nums.get(value) > nums.get(j) ? j : value;
            }
            //置入最小值
            Collections.swap(nums, value, i);
        }
        return nums;
    }

动画图示：

归并排序

稳定性：否

时间复杂度： $O(n\log_{}{n})$ （平均）

归并排序是一个基于分治思想实现的十分高效的稳定排序算法，它旨在将整个集合分段递归处理再进行归并，最终合并为一个有序的序列．

显然的，在归并排序中，最为核心的操作就是＂归并＂(merge)，该操作指的是将两个有序序列合并为一整个有序集合的操作，归并排序的执行是依赖于归并操作的．

归并操作大体可分为以下几步：

按序同时遍历left和right两个ArrayList，使用两个变量来维护索引位置
枚举比较，将较小的值放入目标集合nums
将进行操作的集合对应的下标索引后移一位
重复以上操作直至遍历完其中一个集合
将剩下的非空集合中的所有元素置入目标集合nums中完成合并

为了保证算法的稳定性，在比较过程中，当left.get(i) <= right.get(j)时就应进行置入操作，以避免改变相同元素的位置顺序．

由于我们操作的是两个有序集合，因此每次比较时取出的最小值就是未遍历集合中的最小值，按序放入目标集合后即为从小到大的顺序置入，因此可以认为合并操作后目标集合中的元素是一个有序的序列．

对于merge操作实现如下：

public static void merge(ArrayList nums, ArrayList left, ArrayList right) {
    int i = 0, j = 0, k = 0;
    while (i < left.size() && j < right.size()) {
        if (left.get(i) <= right.get(j)) {
            nums.set(k, left.get(i));
            i++;
        } else {
            nums.set(k, right.get(j));
            j++;
        }
        k++;
    }
    for (; i < left.size(); i++, k++) {
        nums.set(k, left.get(i));
    }
    for (; j < right.size(); j++, k++) {
        nums.set(k, right.get(j));
    }
}

对于分治法的归并排序实现，为了使操作尽可能快，我们应当让分解出来的集合长度尽可能小．

为此，首先我们检查给定集合的长度．

当集合长度仅为1的时候，由于仅有一个元素的存在所以该集合已经是有序的，没有再进行分解的必要，直接返回即可．

那么当集合长度大于1的时候，我们又无法确定该集合是否有序，因此我们尽可能平均地将其分割成两半，再递归地分别对于两边的子集合进行检查．

如果我们发现分解后左右两边的集合都是有序的，那么此时我们可以使用归并操作将它们合并为一个有序集合，否则重复进行分解操作．

重复进行该流程，最终通过对于子集合的合分解合并处理将整个集合变为有序．

实现如下：

public static void mergeSort(ArrayList nums) {
    if (nums.size() <= 1) {
        return;
    }
    int middle = nums.size() / 2;
    ArrayList left = new ArrayList<>(nums.subList(0, middle));
    ArrayList right = new ArrayList<>(nums.subList(middle, nums.size()));
    mergeSort(left);
    mergeSort(right);
    merge(nums, left, right);
}

动画图示：

参考文章：

https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95

https://oi-wiki.org/basic/sort-intro/

动画图示来自：

https://visualgo.net/zh