数据结构与算法：思考排序

相比无序数据，人类更喜欢有序的，比如我们会整理房间，我们会努力组织语言以便让别人更容易理解，等等。提升效率当然是一个原因，比如字典（很难想象一本乱序的字典要如何使用），但还有个我个人觉得很重要的因素是：人是智能体。减熵是智能的一种表现，人类有一种几乎是本能去降低无序性和不确定性的趋向。因为计算机需要供人类使用，排序自然就是一个非常基本且重要的任务了。事实也是如此，我们平时在用代码完成特定任务时，排序也经常会出现在其中，而且往往是处理和分析的第一步。而对计算机本身来说其实并不在乎，就像 ”人工智能“ 也是我们强加给他们的一样，只是因为我们希望他们能够理解人类并为人类服务。所以我们这节主要探讨一下计算机中的排序。为了能够更简单地说明问题，我们假定要排序的是一系列正整数，且按升序排列。

各种排序算法

好了，现在给定一串规模为 n 的乱序的正整数，如何对其从小到大排列？

我觉得最先想到的方法可能是这样的：

  • 每次依次看过去，从中选出最小的放在（交换）对应位置
  • 然后一直选，依次放（交换），到只剩下一个元素为止

时间复杂度：

  • 最坏情况、最好情况和平均情况都是 O(n^2)，因为要看完所有的元素才能知道哪个是最小的（即使本来排好了，它也不知道）。
  • 即：n + (n-1) + ... + 1 = (1+n)*n/2，也就是说无论是什么顺序，每次找最小值都要把剩下的元素挨个看一遍。

空间复杂度：辅助空间为 O(1)，因为要把每次的最小值存下来。这种算法有个名字叫：选择排序。

然后你想，不对呀，如果有些数字本来就是连续排好的，那就可以不用每次找最大最小值了，这不就可以改进算法吗？于是，你可能想这么去做：

  • 相邻两个元素对比，大的放后面，该元素继续与下个元素对比，直到最大的元素交换到最后为止
  • 重复上面的过程，一直到最后一个元素为止

如果有部分数字是连续排好的，那么这些数字因为比较后不满足条件（前面的比后面的大），所以并没有实际执行，这样算法效率就提高了。

时间复杂度：

  • 最坏情况：n + (n-1) + ... + 1 = (1+n)*n/2，O(n^2)
  • 最好情况：需要检查 n 个元素，所以为 O(n)
  • 平均情况：也就是最坏情况每个值不一定正好就是剩余元素的规模，期望是 1/2 的规模，所以也为 O(n^2)

空间复杂度：辅助空间为 O(1)，存储交换时的临时元素。这个算法是：冒泡排序，想象一下，像不像轻的往上浮重的往下降。

不过你可能又发现个小问题：对已经排好有序的，虽然不会执行交换，但还是会比较的呀，因此如果能把已经排好顺序的位置标记一下，那块就不用再排了，这样就能进一步提高效率了。

想到已经排好序的，你可能又能发现一个小问题：如果有一小部分应该在前面的数字在已经排好序的后面，此时它们每次只能移动一个位置，如果从右边开始，一次就从已经排好序的一块中移过去了。于是，你想能否一次左边再一次右边这样像钟摆一样进行冒泡，这样就会进一步减少比较次数（交换次数并不减少）。这种排序算法叫：鸡尾酒排序，应该就是像酒一样摇来摇去吧。

我们稍微休息一下，现在如果问你，还能想到什么方法？如果你是第一次接触可能一下子还不容易想到，但是如果我们稍微用一点点数学的方法，就又可以马上想到了。第一个用到的方法是：归纳法。我们现在假设 n-1 个数字已经排好了，这时候来了第 n 个元素怎么将它放到应该的位置？然后递归这个过程就完成了排序。转为循环的思路就是：

  • 拿出第一个元素，假设就是排好的；取出新的元素与已经排好的依次对比
  • 如果该元素大于已排序的元素，就继续与下个元素对比，直到下个元素比它大为止

需要注意的是，实际操作时反过来（从后面开始对比）会更容易些（因为我们一般会放在数组中），如果已排序元素大，就把已排序的往后挪一位，腾出空间给新的元素。

时间复杂度：

  • 最坏情况：很显然是数字正好反序时，复杂度为：1+...+n = (1+n)*n/2，即 O(n^2)
  • 最好情况：很显然是数字正好排好时，复杂度为：1+...+1=n，即 O(n)
  • 平均情况：与前面的冒泡一样，也是 O(n^2)

空间复杂度：辅助空间为 O(1)，存储新的元素。这个算法叫：插入排序。

如果一个序列本来就几乎有序，可以看出插入排序是逼近 O(n) 的，而且操作非常简单（比起冒泡排序）。另外值得注意的是，它和冒泡排序都是稳定排序。

稳定排序是指两个相等的元素在排序前后位置不变。

选择排序不稳定，因为相同的元素前面的那个可能会被提前交换到后面，当然如果使用了 O(n) 空间的话，就也稳定了。

接下来我们仔细分析下这个算法，会发现即使是相隔元素已经排好序的位置也不会额外增加时间，这点就优于冒泡排序（必须是完全排好的），也就是说，相比冒泡排序，插入排序很好的 ”利用“ 了 ”相对有序“ 这个特征。

解释一下这个相对有序：比如： 1 3 2 5 7，1 3 5 7 就表示相对有序，即相对位置已经有序。

那我们自然就有个想法，能不能让这样的相对有序更多一些呢？能想到的第一个办法当然是我随机选择很小的若干个元素，然后抽出来对它们几个先排序，这样的结果不会增加时间复杂度，但！很有可能会增加更多的相对有序的局部结果，这就能提高一些效率。其实就是让插入排序每次一小步变成一大步（通过把序列 ”分割“ 成一块一块）。

具体做时，可以采用 Dk 间隔，也就是每隔 Dm 抽取一个元素先排好，再隔 Dm-1 抽取一个元素排好，以此类推，其中 D 序列为增量序列。因为数据本来是无序的，所以这样的做法等价于随机抽取，而且还能保证每次不会重复抽到元素。如果你想用随机算法抽取，可别忘了，随机算法本身也是有不小的时间消耗哦。

另外，需要注意的是，一般情况下间隔会选择 n/2, n/4… 一直往下走。

时间复杂度：

  • 最坏情况：每次间隔的抽取根本没起作用（本来就是相对有序的），还白白浪费了那么多次排序。这时候就是正常的插入排序+浪费的排序，时间复杂度为 O(n^2)
  • 最好情况：和增量序列的选择有关，但最好情况就是对已经排好序的结果执行增量序列排序，也就是 O(n)+增量序列的复杂度
  • 平均情况：同样与增量序列的选择有关。

Hibbard 增量序列采用 Dk = 2^k -1，最坏情况：T = Θ(n^3/2)，平均情况猜想：O(n^5/4)，还无法证明；

Sedgewick 增量序列采用 9×4^i - 9×2^i + 1 或 4^i - 3×2^i + 1，最坏情况猜想：O(n^4/3)，平均情况猜想：O(n^7/6)，均未证明。

空间复杂度：辅助空间为 O(1)，存储临时元素。这个算法叫：希尔排序。

不错。看来这种数学方法还是有效果的，接下来我们再尝试一种数学方法：分而治之。猜数字的例子已经耳熟能详了，过程与那个类似。我们假设序列分成两份分别都排好序了，这时只需轮流取出小的就完成排序了，递归地思考一下，就是单个元素，每两个排好序，然后不断重复。

  • 单个元素，两两排序组成 n/2 组
  • 分别取出小的，合并成 n/4 组
  • 不断重复到合并完最后两组（最后只有两组），完成排序

时间复杂度：

  • 最好情况、最坏情况、平均情况均为 O(nlogn)

空间复杂度：需要辅助空间 O(n) 存放取出来的元素。这种排序算法叫：归并排序。

那，能否将之前讲的一些优秀思想合起来使用呢？答案当然是肯定的！

我们首先尝试把冒泡和归并的优点结合，利用了分治的思想进行交换。这种做法通过选定一个基准元素（一般随机选择一个元素）将序列分成两组，然后把其他元素放到基准元素的两边，这就把合并动作通过冒泡做了。移动元素的方法有两种：挖坑法和指针交换法。指定左右元素为左右指针，挖坑法将右边指针的元素和基准元素对比，如果大于基准元素，则右指针左移，否则将右指针指向的元素移入坑（基准元素的 index），同时左指针右移。然后从左指针开始做类似操作，最后把基准元素放回 index 位置即可。指针交换法是将右边比基准元素小的与左边与基准元素大的元素互相交换位置，然后不断重复。

时间复杂度：

  • 最坏情况：选中的基准元素正好是最小值或最大值，此时等于做了 n 论，复杂度为 O(n^2)
  • 最好情况、平均情况：每次正好分到中间位置，复杂度为 O(nlogn)

空间复杂度：需要保存每次递归时的局部变量，一般为 O(logn)，最差为 O(n)，这种排序算法是：快速排序。

我们再试试把希尔和归并的优点结合，这其实是利用相对有序+分治的思想。设想如果我们有一组排好序的格子，然后把数据分别填到格子里，格子里的排好整个序列不就排好了吗？

  • 首先按一定规则创建排好序的格子：一般用（最大值-最小值）/（元素数量-1）
  • 遍历序列填入对应格子
  • 对每个格子内部进行排序

时间复杂度：格子的数量×内部排序的耗时 + 创建格子耗时 + 求最大最小值耗时：求最大最小值运算量 n + 创建格子 m + 遍历序列 n + 内部排序 n/m×log(n/m)×m（假设内部排序使用 O(nlogn) 的算法），最后的复杂度显然是：O(n+m+n(logn-logm))。

空间复杂度：格子空间+序列在格子中占用的空间：O(n+m)。这种排序算法叫：桶排序。

上面的这个例子用到的 ”桶“ 的思想和之前所有的算法均不相同，前面的所有算法都是基于元素比较的，但桶排序却是基于元素下标的。那还有没有其他类似的方法可以使用呢？

和桶排序非常类似的就是：把 “桶” 的个数设置为：（最大值-最小值）个，然后遍历元素，将元素与下标相等的位置加 1，这样遍历完就得到了排好序的结果。

时间复杂度：O(n+m)，空间复杂度：O(m)，可以看出这个是桶排序的一种特殊情况，适用于整数、以及最大最小值差别不是特别大时（太大了会有很多空桶，浪费空间）。这种算法叫：计数排序。

和桶排序非常类似的还有一些算法，此时我们应该已经注意到了，这种多半是数据本身与众不同，比如刚刚的计数排序。

那我们现在考虑这么一种情况：要排序的最大最小值相差非常大，但元素规模却很小，这时候会有很多额外用不到的桶被创建出来，很浪费空间。因此，可以这么考虑：将元素按照某一类特征排序，比如分为 0-9 10 个桶，先按照个位放在对应桶里，然后比较十位调整数字位置，一直到最高位。也就是从个位开始，分别对每位执行计数排序，最后得到的顺序就是结果。时间复杂度：O(ndn)，dn 是位数；空间复杂度：O(ndn) 用于保存每一轮的临时结果。这种算法叫：基数排序。

我们再考虑一种情况：要排序的元素非常大的结构体，并不是一个数字，所以移动非常耗时。此时，对给定关键字的排序，我们可以只移动指向结构体的指针（下标）。比如：3 5 4，我们给出的结果应该是：0 2 1，意味着第 0 个元素是 3，第 1 个是 4，第 2 个是 5。对 “下标” 的排序可以使用上面所提到的排序法。这种间接排序法叫做：表排序。

上面的所有排序算法都默认使用数组或链表这种数据结构，也是最基础的数据结构。如果考虑到数据结构，我们还可以使用另外一种特定的排序方法。

二叉堆：一种完全二叉树，分为最大堆和最小堆。前者任何一个父节点都大于等于左右孩子节点；后者相反。

完全二叉树：有 n 个结点的二叉树，对树中结点按从上到下、从左到右顺序编号，编号结点与满二叉树（完美二叉树）中编号结点在二叉树中完全相同。

最大堆堆顶是整个堆中的最大元素，当删除一个堆顶（替换到最后），经过调整，第二大元素会替换上来成为新的堆顶。如果把需要排序的列构建成二叉堆，然后循环删除堆顶元素，最后原来的最大堆就成为了有序数组。

时间复杂度为：O(nlogn)，空间复杂度为：O(1)，这种排序算法就是：堆排序。

排序快慢背后

排序方法 平均时间复杂度 最坏时间复杂度 额外空间复杂度 稳定性
简单选择排序 O(n^2) O(n^2) O(1) 不稳定
冒泡排序 O(n^2) O(n^2) O(1) 稳定
直接插入排序 O(n^2) O(n^2) O(1) 稳定
希尔排序 O(n^d) O(n^2) O(1) 不稳定
归并排序 O(n×logn) O(n×logn) O(n) 稳定
快速排序 O(n×logn) O(n^2) O(logn) 不稳定
桶排序 O(n×logn) or O(n) O(n×logn) or O(n^2) O(n+m) 稳定
计数排序 O(n+m) O(n+m) O(m) 稳定
基数排序 O(n×dn) O(n×dn) O(n×dn) 稳定
堆排序 O(n×logn) O(n×logn) O(1) 稳定

注：表格整理自网络，详见参考文献。

针对上面介绍的这么多算法，我们现在从整体上来思考一下。在不考虑基数和计数排序这种用于特定情况下的算法时，堆排序、桶排序、归并排序和快速排序都能达到不错的性能。

堆排序无需多言，“堆” 这种数据结构让它无论在时间复杂度还是空间复杂度上都表现优异，且是稳定算法。从这里我们也能明显感觉到数据结构的重要性。引用《算法技术手册》中的一句话：“设计一个高效的算法通常是从选择一个合适的数据结构开始的，数据结构通常是在计算机中表示将要解决的问题”。

那么，剩下的几种呢？它们好像都用了某种思想或方法，更抽象地来说，它们都更好地利用了 “信息”。回想一下上节的展开细节，首先是最简单的选择排序，完全把每个元素当作独立的看，每次只利用到了单个元素的信息，所以可以说是 “最差” 的方法了。然后的冒泡排序就聪明一些了，它利用了 “已经排好最终位置的元素” 这个信息，减少了执行次数。接下来的插入排序，即使相隔元素已经排好序的位置也不会额外增加时间，也就是说它比冒泡更进一步，利用了 “相对有序” 这个特征，这也是 “如果序列中有大量局部有序的情况”，插入排序表现会非常出色的原因了「2」，希尔排序正是充分放大了这一点。归并和快排都是基于分治，我觉得是利用了一种并行的思想，其实它们都没有利用插入排序所利用的信息。如果递归元素数量在一定程度后不继续递归而采用插入排序，只要插入排序的效率超过剩余递归的效率，算法的整体效率就能进一步提高。当然，这是有条件的：“局部有序情况比较多”，所以综合考虑其实这也做没有太多意义。不过，实际中一般会在设定一个阈值，阈值内使用插入排序，阈值外使用快排，能比较有效地提高排序效率「2」。桶排序与前面几种相比比较特殊，它没利用 “比较”，而是想一次把一组确定，它进一步优化了插入排序利用信息的方法，从被动转为主动，所以桶排序期望的性能可以达到 O(n)，我的理解是它 “分层次” 地降低了不确定性。如果能够根据数据分布生成桶（或许用分治的方法？）且不增加时间复杂度，那一定会是一个突破。

那为什么更好地利用了信息就能提高效率呢？乍一看好像句废话，不过这后面可不那么简单，它蕴藏了信息论中关于不确定性（熵）的观点。放在排序这里就是：一个元素尽量与跟自己相近的元素比较，避免与跟自己差距过于明显的元素比较。从信息论的角度来说就是——在选择对象概念均等的条件下，获得的信息量最大。也就是说，在面临不确定性时，我们应该利用已知的信息（有些东西已经是确定的）让选择等可能性（不确定性最大）。这就是熵的思维，当概率相等时，我们额外获取信息能确定的信息量越大。想想，桶排序是不是就是这么做的呢？

说了这么多，到底应该如何选择排序算法呢？《算法技术手册》给了我们一个可以参照的标准：

前提条件 排序算法
只有少量的元素 插入排序
元素几乎已经排好序 插入排序
关注最坏情况下的性能 堆排序
力求在平均情况下具有良好性能 快速排序
元素来自于均匀密集分布的数据源 桶排序
尽可能地少写代码 插入排序
要求稳定性 归并排序

说明：如果有细节看不太明白的也没关系，之后的教程会深入细节，这章只是宏观概览以及从思想和方法上进行理解。不过强烈建议有时间最好能把参考文献的内容看看。

参考文献