3.5.1. 两种简单比较排序方法

这一节先介绍两种最简单的基于比较的排序方法：冒泡排序和选择排序。这两种算法的排序思路都非常简单直观，编程也很方便，但是排序的效率比较低。然而它们的编程确实太方便，冒泡排序还可以很方便地改写成部分排序算法。所以在某些数据量不大，对排序速度要求不高的场合还是很实用的。在学习排序算法的初期也是非常好的数组操作编程练习，所以在目前主流的算法课程中，冒泡和选择依然是最重要的两个入门必学排序算法。

注解

要知道，时间复杂度表示的是一个变化趋势，而不是绝对的速度函数。同样是 \(O(n\log n)\) 的算法，可能速度上也会有不小的差距。而 \(O(n^2)\) 和 \(O(n\log n)\) 的两个算法，在数据规模比较小的时候往往还是 \(O(n^2)\) 时间的算法跑得更快。这里有数学理论上的和编程技术上的两方面的原因：

从数学理论上来看，时间复杂度的函数表达式隐藏了常数系数，这是因为当 \(n\) 越来越大之后，常数系数的影响可以忽略不计，函数的阶就决定了谁快谁慢。但是在数据规模比较小的时候，常数系数的大小就会产生影响。例如一个 \(O(n^2)\) 的算法，它实际工作量为 \({1\over4}n^2\)，另外还有一个 \(O(n\log n)\) 时间的算法，实际工作量为 \(4n\log{n}\)，那么在 \(n\le108\) 的时候，还是那个 \(O(n^2)\) 算法速度快。

从编程技术上来看，要实现 \(O(n\log n)\) 时间的排序算法，就必须用到递归的技术，但是递归调用是有时间开销的。调用函数需要有一系列背后的操作，传值、跳转、返回、复制返回值等，这些都是时间开销。所以当数据量很小的时候，递归的算法并不一定更快。

3.5.1.1. 冒泡排序

冒泡排序通过一系列的“冒泡”过程实现排序。

所谓冒泡过程，就是对一个无序序列中的所有相邻元素对从前向后进行比较，发现逆序对就交换它们的位置，使得较大的元素排在后面。这样一轮冒泡结束后，序列中最大的那个元素就会被推到序列的最后面。

例如对序列 [3, 2, 5, 4, 1] 进行一轮冒泡的过程如下所示（圆括号中是每一步要进行比较的相邻元素对）：

1: [(3, 2), 5, 4, 1] ，(3, 2) 是逆序对，交换为 (2, 3)

2: [2, (3, 5), 4, 1] ，(3, 5) 不是逆序对，不用交换

3: [2, 3, (5, 4), 1] ，(5, 4) 是逆序对，交换为 (4, 5)

4: [2, 3, 4, (5, 1)] ，(5, 1) 是逆序对，交换为 (1, 5)

一轮冒泡结束，得到：[2, 3, 4, 1, 5]

这样，一轮冒泡结束后，原序列中最大的元素5就被移到了序列末尾。这个过程类似于水沸腾时的气泡上浮，最大的元素就是最大的那个气泡，它总是先浮出水面，所以叫做冒泡过程。

从这个示例也可以看出，一轮冒泡并不能完成排序，它只能把最大的元素推到序列末尾，但其他元素是不能保证有序的。为了完成整个序列的排序，就需要对序列进行多次冒泡，直到整个序列都是有序的为止，这就是冒泡排序的思路。

对一个长度为 \(n\) 的无序序列 \(S\) 进行一轮冒泡后，由于最大的元素已经被放置到了最后的 \(S[n-1]\) 位置，所以我们可以认为现在序列由两个子序列构成，其中前 \(n-1\) 个元素构成的子序列 \(S[0:n-1]\) 是无序的，最后一个元素单独构成一个已经有序的子序列 \(S[n-1:n]\)。

接下来我们对仍然无序的子序列 \(S[0:n-1]\) 再进行一轮冒泡，其中最大的元素，也就是整个序列中第2大的元素就会被推到这个子序列的最后一个位置 \(S[n-2]\)。于是现在原序列中，前 \(n-2\) 个元素构成的子序列 \(S[0:n-2]\) 是无序的，而最后2个元素构成的子序列 \(S[n-2:n]\) 已经有序了。

每进行一轮这样的冒泡，序列后部的有序子序列就会增加1个元素，而前部的无序子序列就会缩短1个元素。因此我们可以循环进行 \(n-1\) 轮这样的冒泡，整个序列就排序完成了。

例如对序列 [3, 2, 5, 4, 1] 进行冒泡排序，可以看到下面这样的一个过程（方括号中为尚未完成排序的无序部分，圆括号中为已经有序的部分）：

   [3, 2, 5, 4, 1]

1: [2, 3, 4, 1](5)

2: [2, 3, 1](4, 5)

3: [2, 1](3, 4, 5)

4: [1](2, 3, 4, 5)

到第4轮过后，无序子序列的长度已经变为1，无泡可冒了，整个冒泡排序过程结束。

以元素比较为基本运算计算冒泡排序的工作量。对一个长度为 \(k\) 的序列进行一轮冒泡，需要进行 \(k-1\) 次元素比较。对一个长度为 \(n\) 的序列进行一次冒泡排序，一共需要进行 \(n-1\) 轮冒泡。各轮冒泡所处理的子序列长度分别为 \(n,n-1,\dots,2\)。故整个冒泡排序要进行的元素比较次数，即工作量为：

\[W(n)=(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}\]

这个工作量无论原序列中的元素有序度如何，都是不增不减，恰好这么多次。所以冒泡排序最好情况、最差情况、平均情况的时间复杂度都是 \(O(n^2)\)。

冒泡排序在工作过程中，只需要有一个临时变量用来进行元素交换，因此它的空间复杂度为常数级 \(O(1)\)。

另外，冒泡排序是稳定排序，为什么？请思考。

冒泡排序的改进

对冒泡排序还可以进行一些小小的改进。我们知道，如果一个序列本身已经有序了，那么对它进行一轮冒泡过程就不会发生元素交换。反之亦然，如果在一轮冒泡过程中没有发生元素交换，说明每一对相邻元素都是顺序正确的，这就意味着这个序列已经全部有序了。所以我们可以在每一轮冒泡的过程中对元素交换进行计数，一轮结束后如果没有发生交换，我们可以直接终止排序过程，因为这时候排序已经完成了。

经过这样的改进，对于那些原本就基本有序的序列，能节约很多时间。最好的情况下，如果原序列就是一个有序序列，那么一轮冒泡之后排序就完成了，所以最好情况的时间复杂度就优化为 \(O(n)\) 线性时间了。

下面是一个优化过的冒泡算法C++程序，并且添加了显示排序过程的调试语句。

#include <cstdio>

void print(int d[], int n);     // 输出数组 d[] 的前 n 个元素，用于调试

void bubble_sort(int d[], int n);

int main()
{
        int n, d[100];
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) scanf("%d", &d[i]);
        bubble_sort(d, n);

        printf("Bubble sort finished\n");
        print(d, n);

        return 0;
}

void bubble_sort(int d[], int n)
{
        int swap_cnt, tmp;
        for (int m = n; m > 1; --m) {
                swap_cnt = 0;
                for (int i = 0; i < m - 1; ++i) {
                        if (d[i] > d[i+1]) {
                                tmp = d[i];
                                d[i] = d[i+1];
                                d[i+1] = tmp;
                                ++swap_cnt;
                        }
                }
                if (!swap_cnt) return;
                // 调试语句
                printf("Bubble from d[0] to d[%d]: ", m - 1);
                print(d, n);
        }
}

void print(int d[], int n)
{
        printf("%d", d[0]);
        for (int i = 1; i < n; ++i) printf(" %d", d[i]);
        printf("\n");
}

思考

再请思考一下两个问题：

1. 如果我们要从大到小的排逆序，当然也要保持稳定性，应该怎么写冒泡排逆序的程序。

2. 如果每一轮冒泡不是从前向后进行，而是反过来从后向前进行，会出现什么情况？（提示：在水里，气泡会上浮，那么石头呢？）

冒泡排序经过一些改变可以构造一些简单的应用，在数据量不大的情况下，由于思路直观、编程简单，也很有一些应用价值。

寻找k位数

利用冒泡过程，我们可以很简单地实现在一个无序序列中寻找k位数，即第k小的那个数。事实上，在一个长度为 \(n\) 的序列中，第k小的数就是第 \(n-k\) 大的那个数。所以最简单粗暴的方法，进行 \(n-k\) 轮冒泡就可以得到k位数。但是实际上还是有一些可以优化的余地的，比如上面所述的那个冒泡排序的优化就可以用上。又比如说，假如元素数 \(n\) 很大而 \(k\) 很小，那么要进行的冒泡轮数 \(n-k\) 就会很大，这就有点舍近求远的问题了，请思考一下这种情况要怎么进行优化，并完成下面的编程练习：

练习

编写一个利用冒泡寻找k位数的程序，输入有两行，第一行为两个整数 \(n, k\)，其中 \(1\lt n\le10^3;1\le k\le n\)，第二行为 \(n\) 个整数，取值都在 int 型范围内。

要求利用冒泡过程求解，并尽量进行优化。

输出：一行，一个整数，即输入的 \(n\) 个整数序列中的k位数。

部分排序

有时候我们对一个序列只想对它进行部分排序，也就是说只想对其中最小（或最大）的一部分元素完成排序，不需要对所有元素进行排序。比如说有一所名牌大学面向全球招生，全世界有数百万学生报考，最后学校决定总成绩前1000名的学生可以直接录取。这时我们只需要从几百万个分数中挑出最大的1000个。当然我们可以对所有分数进行排序然后取最大的1000个，但是如果我们能部分排序，只排出前1000名就结束，岂不更好？这就是部分排序。

用冒泡排序的思路，可以方便地完成部分排序，请思考一下完成下面的编程练习：

练习

编写一个部分冒泡排序程序，输入有两行，第一行为两个整数 \(n, m\)，其中 \(1\lt n\le10^3;1\le m\le n\)，第二行为 \(n\) 个整数，取值都在 int 型范围内。

要求对输入的 \(n\) 个整数的序列进行长度为 \(m\) 的部分排序，即只排出从最小到第 \(m\) 小的 \(m\) 个元素，将它们依序放在最前面的 \(m\) 个位置上，其余元素无关顺序地罗列在后面即可。

输出：完成部分排序的序列，数和数之间用一个空格间隔，第一个数的前面和最后一个数的后面不允许出现空格。

例如：输入 \(n=5,m=2\)，输入数据为 3 2 5 4 1，则输出 1 2 x x x，三个 x 表示另外3个数，其顺序无所谓。

3.5.1.2. 选择排序

选择排序也是一种基于元素比较的简单排序算法，它的思路甚至比冒泡排序更加简单粗暴，就是通过多轮挑选，每次从未排序子序列中选出最大者（或最小者）并将其放至尾部（或头部）的操作完成排序。刚开始的时候整个序列都是未排序子序列，随着一轮一轮的选择，未排序子序列越来越短，直到只剩最后一个元素，整个选择排序就完成了。

对于长度为 \(n\) 的序列 \(A\)，选择排序的算法如下：

选择排序算法

\(\text{SelectionSort}(A,n):\)

\(\text{FOR }k\leftarrow n-1 \text{ TO }1\text{ DO}\)

\(i\leftarrow\text{argmax}\{A[0],\dots,A[k]\}\) // argmax{…} 用于寻找最大值出现的位置

\(\text{Swap}(A[i], A[k])\) // 交换找到的最大值 A[i] 和 本轮选择的子序列尾元素 A[k]

例如对序列 [3, 2, 5, 4, 1] 进行选最大方式的选择排序，过程如下（方括号中为尚未完成排序的无序部分，圆括号中为已经有序的部分）：

   [3, 2, 5, 4, 1]

1: [3, 2, 1, 4](5)   选出最大值5和末尾的1交换

2: [3, 2, 1](4, 5)   选出最大值4和末尾的4交换

3: [1, 2](3, 4, 5)   选出最大值3和末尾的1交换

4: [1](2, 3, 4, 5)   选出最大值2和末尾的1交换

经过4轮选最大并交换到末尾的操作之后，未排序部分长度减为1，已经无最大数可选，排序结束。

练习

模仿冒泡排序示例程序的样子，编写输入一个整数序列并进行选择排序的程序。

为了从 \(k\) 个元素中找出最大的那个元素，我们知道必须进行 \(k-1\) 次元素比较。为了完成选择排序，必须依次在 \(n\) 个元素、\(n-1\) 个元素，……，直到2个元素的子序列中选择最大者。所以和冒泡排序一样，选择排序的工作量为：

\[W(n) = (n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}\]

和冒泡排序一样，无论原序列中的元素排列情况如何，都是这么多次元素比较，不多不少，所以无论何种情况，选择排序的时间复杂度都是 \(O(n^2)\)。

和冒泡排序一样，选择排序只需要一个临时变量用来交换元素，所以空间复杂度为常数级 \(O(1)\)。

和冒泡排序不一样，选择排序是不稳定排序，请自己思考原因。

和冒泡排序不一样，选择排序没有什么明显可以优化的情况，时间复杂度永远是稳稳的 \(O(n^2)\)。但是总体来说它在实际应用中运行速度是比冒泡排序快不少的，事实上选择排序的发明本身就源自于对冒泡排序的一次改进！这是为什么呢？

仔细观察比对我们的两个示例过程，想一想这两种排序过程中的相同点和不同点，不难发现本质上冒泡和选择两种算法都是通过多轮“选出最大（小）者放到尾（头）部”的操作来进行排序的。所以它们本质上是同一类排序算法。但是冒泡排序在一轮冒泡中，为了让最大（小）者顺利到达尾（头）部，需要多次交换元素，最坏的情况交换次数和比较次数相同，都是 \(k-1\) 次。而选择排序在一轮选择中，同样也是进行 \(k-1\) 次比较，却只需要最后来一次交换就能让被选中者到达预定位置。形象地说，冒泡排序时最大（小）元素是爬过去的，选择排序时最大（小）元素是飞过去的。这就是选择排序比冒泡排序的实际运行速度要快的原因。

在应用上，冒泡排序能做到的所有事情选择排序都可以做到，比如寻找k位数、部分排序等，而且速度往往会更快一些，但同样只能限于数据量不大、对效率要求不高的场景。如果要编写高效率算法，无论冒泡还是选择都是不行的。它们一般用于排序算法入门学习，不过由于编程简单不易出错，往往可以用来临场快速编写一些考场工具，比如用于后台打数据表，有时候还确实挺实用的。