排序算法

发表于 2019-03-04 更新于 2022-09-13 阅读次数：

排序算法。

写在开头：对排序算法的整体理解

我的一个想法是，这些不同名字的算法都是一种思想，不能针对一种思想谈时空复杂度，如果要谈时空复杂度，就针对一个具体的实现来谈。

比如说，通常情况下，归并排序需要使用 $O(n)$ 的空间复杂度，但是如果使用自底向上的方式，就可以实现原地排序。这就是我要说的不要针对算法思想谈论时空复杂度，要针对具体实现讨论时空复杂度。还有别的例子：不同人实现的快速排序算法，时空复杂度可能有很大的差别。最基本的快速排序和三路快速排序的时空复杂度也是不一样的。

另外，也不是非要使用单纯的一种排序算法，有可能是多种算法相结合的。比如，JDK 的类库中，快速排序中，当待排序的元素数小于某个值的时候，就是用插入排序，因为在数组比较小的情况下，插入排序的速度也很快。同时也可以有效减少快速排序使用的系统栈的数量，防止栈溢出。

要根据不同的场景选择不同的算法。不是说快速排序很厉害，所有场景都可以使用快速排序。还要考虑这个排序算法是不是稳定的，有些场景有需要稳定的排序算法。或者有些场景下，无法把所有要排序的内容读进内存，还需要是其他类型的排序算法。

分类

排序算法主要有：插入排序、交换类排序、选择类排序、二路归并排序、基数排序、外部排序。

冒泡排序 Bubble sort

核心思想

第一次循环，从数组的第一个元素开始，和它右边相邻的元素进行比较，如果比右边的数大就交换位置。如果比右边的数小，就不交换，选择右边的数继续和右边的数作比较。一直到倒数第二个元素和倒数第一的元素比较完，结束第一轮循环。这样一轮下来，能够把最大的元素移到数组最右边。第二次循环，继续从第一个元素开始，一对一对的比较，同样是只要左边比右边的大，就交换位置，一直把最大的元素交换到倒数第二个位置，因为第一轮已经把最大的数放在最后一个位置了。

优化的思路

可以设置一个计数器，统计每一轮交换操作的次数，如果某一轮循环结束之后，交换的次数为 0，说明数组已经有序，可以直接跳出循环。

复杂度

平均时间复杂度 $O(n^2)$。

最坏时间复杂度 $O(n^2)$。

最优时间复杂度$O(n)$。

拓展

还有一种往返移动的冒泡排序方法，叫做鸡尾酒排序，参考：鸡尾酒排序 - Wikipedia。

参考资料

冒泡排序 - Wikipedia

插入排序 Insertion sort

核心思想

从数组的第二个元素开始，每次选择一个元素，和这个元素左边相邻的元素作比较，如果比它左边的元素小，就和它左边的元素交换位置，交换位置继续和它左边的元素比较，一直交换到不小于它左边相邻的元素或者它已经到了数组最左边为止。这就相当于把这个数“插入”到了左边最适合它的位置。

排序结果是非逆序。

优化的思路

对两个元素进行一次交换操作，要用三条语句来完成，即 ① 把第一个数放到临时变量，② 把第二个数放到第一个数的位置，③ 把临时变量放到第一个数的位置。

其实，要把一个元素插入有序序列，并不需要从右向左和每个元素依次交换，可以先通过比较操作确定要把这个元素插到哪里，然后把这个元素存到临时变量中，然后把这个元素前边的元素从后往前依次向后移一位。把最终的位置空出来就好了。

比如，打个比喻，学生时代升国旗一般一个班占成一列，加入老师让最后一个学生站到前边来，他并不需要和他前边的同学一个一个交换位置，只需要他前边的同学依次往后挪一个位置，把最前方空一个位置出来给他就可以了。

优化之前，假如把一个数插入有序序列当中，加入有序序列长度为 $N$，而这个数在有序序列中是最小的数。那么，他要和 $N$ 个数交换位置，每次交换需要三条语句进行操作，相当于进行了 $3N$ 次赋值操作。

优化之后，有序序列中的 $N$ 个数每个数向后移动一位，只需要 $N+2$ 次赋值操作。赋值操作次数大约变成了原来的三分之一。效率大大提高。

选择排序 Selection sort

核心思想

第一轮循环，从数组中选出最小的元素，和数组第一个元素交换位置，第二轮循环，从数组第二个到最后一个元素中选出来最小的元素，和第二个元素交换位置。以此类推，只要把所有元素都归位。这个算法是每次都先从剩下的元素中选出来一个最小元素，可以理解为不需要管已经排好序的部分，只需要从剩下的元素中选择出来最小的元素即可。

public static void selectionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if(arr[j] < arr[minIndex]){
                minIndex = j;
            }
        }
        swap(arr, i, minIndex);
    }
}

缺点

选择排序的时间复杂度跟初始顺序的关系不大，初始顺序即使是完全排序的，也还是需要扫描 $N$ 次数组。

冒泡、选择、插入的一个小测试

冒泡、选择、插入排序对比

大小为 10_0000 的 Integer 数组。计时单位为 nano Sec，纳秒。1 秒 = $10^9$ 纳秒。

小测试1

大小倒序排序，对于冒泡和插入来说是最坏情况。

运行结果为：

[Bubble    sort]37156614522 nano Sec ≈ 37 Sec
[Insertion sort]27703624445 nano Sec ≈ 27 Sec
[Selection sort]14952776173 nano Sec ≈ 14 Sec
[Quick     sort]11823755899 nano Sec ≈ 11 Sec
[Arrays.   sort]    6059783 nano Sec ≈ 6 ms

小测试2

数组大小是已排序的，最优情况。

[Bubble    sort]   7490181 nano Sec ≈ 7 ms
[Insertion sort]   8603794 nano Sec ≈ 8 ms
[Selection sort]7398872764 nano Sec ≈ 7 Sec
[Quick     sort]5944729495 nano Sec ≈ 5 Sec
[Arrays.   sort]   5218160 nano Sec ≈ 5 ms

小测试3

使用 java.util.Random 类产生随机数。

[Bubble    sort]54922618215 nano Sec ≈  54 Sec
[Insertion sort]22400064194 nano Sec ≈  22 Sec
[Selection sort]17360812065 nano Sec ≈  17 Sec
[Quick     sort]17448505605 nano Sec ≈  17 Sec
[Arrays.   sort]  138667753 nano Sec ≈ 138 ms

希尔排序 Shell sort

例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再以3为步长进行排序：

排序之后变为：

最后以1步长进行排序（此时就是简单的插入排序了）。

复杂度

《算法》的作者 Sedgewick 在《算法》这本书中写道“透彻理解希尔排序的性能至今（2011年）仍然是一项挑战，实际上，希尔排序是我们唯一无法准确描述其对于乱序数组的性能特征的排序方法。”

选择不同的步长序列，算法的性能会有所不同。

但是，可以肯定的是，希尔排序在最坏的情况下运行时间仍然达不到平方级别。《算法》书中算法 2.3 的实现，最坏情况下的比较次数和 $N^{\frac{3}{2}}$ 成正比。

参考资料

归并排序

归并排序在执行 merge() 时需要 $O(n)$ 的空间。

自顶向下归并排序

核心思想

分治法。将数组平均分为两部分，分别对两部分排序，然后归并。

自底向上归并排序

核心思想

不使用递归的方式来实现。直接对数组进行多轮的归并操作，第一轮两个两个归并，第二轮四个四个归并。一直到数组的前一半和后一半进行归并。

原地归并排序

时间换空间版本

可以把空间复杂度降到 $O(1)$，但是时间复杂度会变成 $O(n^2)$，所以一般没必要这么做，因为一般都是拿空间换时间，很少拿时间换空间。

另外，左大神左程云的算法课程中提到“归并排序内部缓存法”也是一种方法，不过没查到很多资料，下边资料中的英文版没有详细看，不知道是不是，有时间再看一看。

参考资料

In-Place Merge Sort

二路归并 & 插入归并 & 原地归并

In-Place Merge Sort

拓展题目

《剑指Offer》第2版，第51题，求逆序对的问题。

快速排序

核心思想

稳定的快速排序

快速排序其实也可以实现为稳定版本，但是比较难。可以搜“01 stable sort”。这个算法还涉及到一个题目：一个数组，要求把奇数放左部分，偶数放在有部分，且奇数偶数内部原来的相对次序不变，要求空间复杂度 $O(1)$，时间复杂度 $O(n)$。

其他

跟JDK学算法之快速排序

计数排序

排序算法的稳定性

排序算法的稳定性是指，两个相等的元素在排序前和排序后的相对位置不变，也就是两个相等的元素 A 和 B，排序前 A 在 B 的前面，排序后 A 还在 B 的前面，这样的话就说这个排序算法是稳定的。如果排序之后 A 跑到 B 的后边了，那样就说这个排序算法是不稳定的。

其实对于基本类型来说，稳不稳定无所谓，主要是对对象类型而言，稳定有时候很重要。

算法名称	稳定性
冒泡排序	稳定
插入排序	稳定
归并排序	稳定
选择排序	不稳定
快速排序	不稳定
堆排序	不稳定

冒泡排序每次对比，如果两个元素相等，是不会交换位置的，所以冒泡排序是稳定的。
插入排序，因为是从第二个元素开始依次插入到有序序列，如果有两个元素相等，后插入的元素也只会插入到相等元素的后面。也不会改变相对顺序。
选择排序是不稳定的。

比如，{$5_1$, $5_2$, 4, 3, 2, 1}，排完序之后会变成 {1, 2, 3, 4, $5_2$, $5_1$}，可以看到，两个相等的元素 5 的相对位置发生了变化。

实际工作中的应用

总是会提到排序算法的稳定性，但是这个稳定性在实际工作中那些场景中可能会遇到呢？我看到关注这个点的文章比较少，所以想自己搜集一下相关的资料。

我看到的一些文章中说，对于对象的排序可能会需要排序算法是稳定的。

聊聊前端排序的那些事

二次排序

因为一个对象是有不同的性质的，所以可能需要同时按照两种属性来排序，比如说，一个年级某次考试成绩表，要求按班级排序，班级相同的按照成绩由高到低排序。

这个排序可以通过两次排序来实现，第一次针对成绩从高到低排序依次，然后根据班级排序依次。

假如排序算法是不稳定的，第一次是针对成绩排序的，在本例中这一步跟稳定性没有关系。然后第二次排序，假如这个排序算法是不稳定的，那么排序过程中，班级相同的人排到了一起，但是因为排序算法不稳定，原来的相互之间的顺序就丢失了，而原来的相互之间的顺序恰恰是满足大小顺序的。

如果是稳定的排序算法，第二次排序把班级相同的同学排序到了一起，同时相同班级的每个同学的成绩仍然保持第一步排序之后的相对顺序，也就是大小的相对顺序。

拓展

击败Java的排序算法，英文版 Beating Java Sort Performance