两种简单比较排序方法 ++++++++++++++++++++ 这一节先介绍两种最简单的基于比较的排序方法：冒泡排序和选择排序。这两种算法的排序思路都非常简单直观，编程也很方便，但是排序的效率比较低。然而它们的编程确实太方便，冒泡排序还可以很方便地改写成部分排序算法。所以在某些数据量不大，对排序速度要求不高的场合还是很实用的。在学习排序算法的初期也是非常好的数组操作编程练习，所以在目前主流的算法课程中，冒泡和选择依然是最重要的两个入门必学排序算法。 .. note:: 要知道，时间复杂度表示的是一个变化趋势，而不是绝对的速度函数。同样是 :math:`O(n\log n)` 的算法，可能速度上也会有不小的差距。而 :math:`O(n^2)` 和 :math:`O(n\log n)` 的两个算法，在数据规模比较小的时候往往还是 :math:`O(n^2)` 时间的算法跑得更快。这里有数学理论上的和编程技术上的两方面的原因： 从数学理论上来看，时间复杂度的函数表达式隐藏了常数系数，这是因为当 :math:`n` 越来越大之后，常数系数的影响可以忽略不计，函数的阶就决定了谁快谁慢。但是在数据规模比较小的时候，常数系数的大小就会产生影响。例如一个 :math:`O(n^2)` 的算法，它实际工作量为 :math:`{1\over4}n^2`\ ，另外还有一个 :math:`O(n\log n)` 时间的算法，实际工作量为 :math:`4n\log{n}`\ ，那么在 :math:`n\le108` 的时候，还是那个 :math:`O(n^2)` 算法速度快。 从编程技术上来看，要实现 :math:`O(n\log n)` 时间的排序算法，就必须用到递归的技术，但是递归调用是有时间开销的。调用函数需要有一系列背后的操作，传值、跳转、返回、复制返回值等，这些都是时间开销。所以当数据量很小的时候，递归的算法并不一定更快。 冒泡排序 ^^^^^^^^^^^^^^^^^^^^ :strong:`冒泡排序`\ 通过一系列的“冒泡”过程实现排序。 所谓冒泡过程，就是对一个无序序列中的所有相邻元素对从前向后进行比较，发现逆序对就交换它们的位置，使得较大的元素排在后面。这样一轮冒泡结束后，序列中最大的那个元素就会被推到序列的最后面。 例如对序列 [3, 2, 5, 4, 1] 进行一轮冒泡的过程如下所示（圆括号中是每一步要进行比较的相邻元素对）： .. code-block:: none 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就被移到了序列末尾。这个过程类似于水沸腾时的气泡上浮，最大的元素就是最大的那个气泡，它总是先浮出水面，所以叫做冒泡过程。 从这个示例也可以看出，一轮冒泡并不能完成排序，它只能把最大的元素推到序列末尾，但其他元素是不能保证有序的。为了完成整个序列的排序，就需要对序列进行多次冒泡，直到整个序列都是有序的为止，这就是冒泡排序的思路。 对一个长度为 :math:`n` 的无序序列 :math:`S` 进行一轮冒泡后，由于最大的元素已经被放置到了最后的 :math:`S[n-1]` 位置，所以我们可以认为现在序列由两个子序列构成，其中前 :math:`n-1` 个元素构成的子序列 :math:`S[0:n-1]` 是无序的，最后一个元素单独构成一个已经有序的子序列 :math:`S[n-1:n]`\ 。 接下来我们对仍然无序的子序列 :math:`S[0:n-1]` 再进行一轮冒泡，其中最大的元素，也就是整个序列中第2大的元素就会被推到这个子序列的最后一个位置 :math:`S[n-2]`\ 。于是现在原序列中，前 :math:`n-2` 个元素构成的子序列 :math:`S[0:n-2]` 是无序的，而最后2个元素构成的子序列 :math:`S[n-2:n]` 已经有序了。 每进行一轮这样的冒泡，序列后部的有序子序列就会增加1个元素，而前部的无序子序列就会缩短1个元素。因此我们可以循环进行 :math:`n-1` 轮这样的冒泡，整个序列就排序完成了。 例如对序列 [3, 2, 5, 4, 1] 进行冒泡排序，可以看到下面这样的一个过程（方括号中为尚未完成排序的无序部分，圆括号中为已经有序的部分）： .. code-block:: none [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，无泡可冒了，整个冒泡排序过程结束。 以元素比较为基本运算计算冒泡排序的工作量。对一个长度为 :math:`k` 的序列进行一轮冒泡，需要进行 :math:`k-1` 次元素比较。对一个长度为 :math:`n` 的序列进行一次冒泡排序，一共需要进行 :math:`n-1` 轮冒泡。各轮冒泡所处理的子序列长度分别为 :math:`n,n-1,\dots,2`\ 。故整个冒泡排序要进行的元素比较次数，即工作量为： .. math:: W(n)=(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2} 这个工作量无论原序列中的元素有序度如何，都是不增不减，恰好这么多次。所以冒泡排序最好情况、最差情况、平均情况的时间复杂度都是 :math:`O(n^2)`\ 。 冒泡排序在工作过程中，只需要有一个临时变量用来进行元素交换，因此它的空间复杂度为常数级 :math:`O(1)`\ 。 另外，冒泡排序是稳定排序，为什么？请思考。 **冒泡排序的改进** 对冒泡排序还可以进行一些小小的改进。我们知道，如果一个序列本身已经有序了，那么对它进行一轮冒泡过程就不会发生元素交换。反之亦然，如果在一轮冒泡过程中没有发生元素交换，说明每一对相邻元素都是顺序正确的，这就意味着这个序列已经全部有序了。所以我们可以在每一轮冒泡的过程中对元素交换进行计数，一轮结束后如果没有发生交换，我们可以直接终止排序过程，因为这时候排序已经完成了。 经过这样的改进，对于那些原本就基本有序的序列，能节约很多时间。最好的情况下，如果原序列就是一个有序序列，那么一轮冒泡之后排序就完成了，所以最好情况的时间复杂度就优化为 :math:`O(n)` 线性时间了。 下面是一个优化过的冒泡算法C++程序，并且添加了显示排序过程的调试语句。 .. literalinclude:: ../../codes/251_bubble_sort.cpp :language: c++ .. admonition:: 思考 再请思考一下两个问题： 1. 如果我们要从大到小的排逆序，当然也要保持稳定性，应该怎么写冒泡排逆序的程序。 2. 如果每一轮冒泡不是从前向后进行，而是反过来从后向前进行，会出现什么情况？（提示：在水里，气泡会上浮，那么石头呢？） 冒泡排序经过一些改变可以构造一些简单的应用，在数据量不大的情况下，由于思路直观、编程简单，也很有一些应用价值。 **寻找k位数** 利用冒泡过程，我们可以很简单地实现在一个无序序列中寻找k位数，即第k小的那个数。事实上，在一个长度为 :math:`n` 的序列中，第k小的数就是第 :math:`n-k` 大的那个数。所以最简单粗暴的方法，进行 :math:`n-k` 轮冒泡就可以得到k位数。但是实际上还是有一些可以优化的余地的，比如上面所述的那个冒泡排序的优化就可以用上。又比如说，假如元素数 :math:`n` 很大而 :math:`k` 很小，那么要进行的冒泡轮数 :math:`n-k` 就会很大，这就有点舍近求远的问题了，请思考一下这种情况要怎么进行优化，并完成下面的编程练习： .. admonition:: 练习 编写一个利用冒泡寻找k位数的程序，输入有两行，第一行为两个整数 :math:`n, k`\ ，其中 :math:`1\lt n\le10^3;1\le k\le n`\ ，第二行为 :math:`n` 个整数，取值都在 ``int`` 型范围内。 要求利用冒泡过程求解，并尽量进行优化。 输出：一行，一个整数，即输入的 :math:`n` 个整数序列中的k位数。 **部分排序** 有时候我们对一个序列只想对它进行部分排序，也就是说只想对其中最小（或最大）的一部分元素完成排序，不需要对所有元素进行排序。比如说有一所名牌大学面向全球招生，全世界有数百万学生报考，最后学校决定总成绩前1000名的学生可以直接录取。这时我们只需要从几百万个分数中挑出最大的1000个。当然我们可以对所有分数进行排序然后取最大的1000个，但是如果我们能部分排序，只排出前1000名就结束，岂不更好？这就是部分排序。 用冒泡排序的思路，可以方便地完成部分排序，请思考一下完成下面的编程练习： .. admonition:: 练习 编写一个部分冒泡排序程序，输入有两行，第一行为两个整数 :math:`n, m`\ ，其中 :math:`1\lt n\le10^3;1\le m\le n`\ ，第二行为 :math:`n` 个整数，取值都在 ``int`` 型范围内。 要求对输入的 :math:`n` 个整数的序列进行长度为 :math:`m` 的部分排序，即只排出从最小到第 :math:`m` 小的 :math:`m` 个元素，将它们依序放在最前面的 :math:`m` 个位置上，其余元素无关顺序地罗列在后面即可。 输出：完成部分排序的序列，数和数之间用一个空格间隔，第一个数的前面和最后一个数的后面不允许出现空格。 例如：输入 :math:`n=5,m=2`\ ，输入数据为 ``3 2 5 4 1``\ ，则输出 ``1 2 x x x``\ ，三个 ``x`` 表示另外3个数，其顺序无所谓。 选择排序 ^^^^^^^^^^^^^^^^^^^^ :strong:`选择排序`\ 也是一种基于元素比较的简单排序算法，它的思路甚至比冒泡排序更加简单粗暴，就是通过多轮挑选，每次从未排序子序列中选出最大者（或最小者）并将其放至尾部（或头部）的操作完成排序。刚开始的时候整个序列都是未排序子序列，随着一轮一轮的选择，未排序子序列越来越短，直到只剩最后一个元素，整个选择排序就完成了。 对于长度为 :math:`n` 的序列 :math:`A`\ ，选择排序的算法如下： .. admonition:: 选择排序算法 :math:`\text{SelectionSort}(A,n):` :math:`\text{FOR }k\leftarrow n-1 \text{ TO }1\text{ DO}` :math:`i\leftarrow\text{argmax}\{A[0],\dots,A[k]\}` // argmax{...} 用于寻找最大值出现的位置 :math:`\text{Swap}(A[i], A[k])` // 交换找到的最大值 A[i] 和 本轮选择的子序列尾元素 A[k] 例如对序列 [3, 2, 5, 4, 1] 进行选最大方式的选择排序，过程如下（方括号中为尚未完成排序的无序部分，圆括号中为已经有序的部分）： .. code-block:: none [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，已经无最大数可选，排序结束。 .. admonition:: 练习 模仿冒泡排序示例程序的样子，编写输入一个整数序列并进行选择排序的程序。 为了从 :math:`k` 个元素中找出最大的那个元素，我们知道必须进行 :math:`k-1` 次元素比较。为了完成选择排序，必须依次在 :math:`n` 个元素、:math:`n-1` 个元素，......，直到2个元素的子序列中选择最大者。所以和冒泡排序一样，选择排序的工作量为： .. math:: W(n) = (n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2} 和冒泡排序一样，无论原序列中的元素排列情况如何，都是这么多次元素比较，不多不少，所以无论何种情况，选择排序的时间复杂度都是 :math:`O(n^2)`\ 。 和冒泡排序一样，选择排序只需要一个临时变量用来交换元素，所以空间复杂度为常数级 :math:`O(1)`\ 。 和冒泡排序不一样，选择排序是不稳定排序，请自己思考原因。 和冒泡排序不一样，选择排序没有什么明显可以优化的情况，时间复杂度永远是稳稳的 :math:`O(n^2)`\ 。但是总体来说它在实际应用中运行速度是比冒泡排序快不少的，事实上选择排序的发明本身就源自于对冒泡排序的一次改进！这是为什么呢？ 仔细观察比对我们的两个示例过程，想一想这两种排序过程中的相同点和不同点，不难发现本质上冒泡和选择两种算法都是通过多轮“选出最大（小）者放到尾（头）部”的操作来进行排序的。所以它们本质上是同一类排序算法。但是冒泡排序在一轮冒泡中，为了让最大（小）者顺利到达尾（头）部，需要多次交换元素，最坏的情况交换次数和比较次数相同，都是 :math:`k-1` 次。而选择排序在一轮选择中，同样也是进行 :math:`k-1` 次比较，却只需要最后来一次交换就能让被选中者到达预定位置。形象地说，冒泡排序时最大（小）元素是爬过去的，选择排序时最大（小）元素是飞过去的。这就是选择排序比冒泡排序的实际运行速度要快的原因。 在应用上，冒泡排序能做到的所有事情选择排序都可以做到，比如寻找k位数、部分排序等，而且速度往往会更快一些，但同样只能限于数据量不大、对效率要求不高的场景。如果要编写高效率算法，无论冒泡还是选择都是不行的。它们一般用于排序算法入门学习，不过由于编程简单不易出错，往往可以用来临场快速编写一些考场工具，比如用于后台打数据表，有时候还确实挺实用的。