出自matrix67.com
今天我正式开始按照我的目录写我的OI心得了。我要把我所有学到的OI知识传给以后千千万万的OIer。以前写过的一些东西不重复写了，但我最后将会重新整理，使之成为一个完整的教程。
按照我的目录，讲任何东西之前我都会先介绍时间复杂度的相关知识，以后动不动就会扯到这个东西。这个已经写过了，你可以在这里看到那篇又臭又长的文章。在讲排序算法的过程中，我们将始终围绕时间复杂度的内容进行说明。
我把这篇文章称之为“从零开始学算法”，因为排序算法是最基础的算法，介绍算法时从各种排序算法入手是最好不过的了。
给出n个数，怎样将它们从小到大排序？下面一口气讲三种常用的算法，它们是最简单的、最显然的、最容易想到的。选择排序(Selection Sort)是说，每次从数列中找出一个最小的数放到最前面来，再从剩下的n-1个数中选择一个最小的，不断做下去。插入排序(Insertion Sort)是，每次从数列中取一个还没有取出过的数，并按照大小关系插入到已经取出的数中使得已经取出的数仍然有序。冒泡排序(Bubble Sort)分为若干趟进行，每一趟排序从前往后比较每两个相邻的元素的大小（因此一趟排序要比较n-1对位置相邻的数）并在每次发现前面的那个数比紧接它后的数大时交换位置；进行足够多趟直到某一趟跑完后发现这一趟没有进行任何交换操作（最坏情况下要跑n-1趟，这种情况在最小的数位于给定数列的最后面时发生）。事实上，在第一趟冒泡结束后，最后面那个数肯定是最大的了，于是第二次只需要对前面n-1个数排序，这又将把这n-1个数中最小的数放到整个数列的倒数第二个位置。这样下去，冒泡排序第i趟结束后后面i个数都已经到位了，第i+1趟实际上只考虑前n-i个数（需要的比较次数比前面所说的n-1要小）。这相当于用数学归纳法证明了冒泡排序的正确性：实质与选择排序相同。上面的三个算法描述可能有点模糊了，没明白的话网上找资料，代码和动画演示遍地都是。
这三种算法非常容易理解，因为我们生活当中经常在用。比如，班上的MM搞选美活动，有人叫我给所有MM排个名。我们通常会用选择排序，即先找出自己认为最漂亮的，然后找第二漂亮的，然后找第三漂亮的，不断找剩下的人中最满意的。打扑克牌时我们希望抓完牌后手上的牌是有序的，三个8挨在一起，后面紧接着两个9。这时，我们会使用插入排序，每次拿到一张牌后把它插入到手上的牌中适当的位置。什么时候我们会用冒泡排序呢？比如，体育课上从矮到高排队时，站队完毕后总会有人出来，比较挨着的两个人的身高，指挥到：你们俩调换一下，你们俩换一下。
这是很有启发性的。这告诉我们，什么时候用什么排序最好。当人们渴望先知道排在前面的是谁时，我们用选择排序；当我们不断拿到新的数并想保持已有的数始终有序时，我们用插入排序；当给出的数列已经比较有序，只需要小幅度的调整一下时，我们用冒泡排序。
我们来算一下最坏情况下三种算法各需要多少次比较和赋值操作。
选择排序在第i次选择时赋值和比较都需要n-i次（在n-i+1个数中选一个出来作为当前最小值，其余n-i个数与当前最小值比较并不断更新当前最小值），然后需要一次赋值操作。总共需要n(n-1)/2次比较与n(n-1)/2+n次赋值。
插入排序在第i次寻找插入位置时需要最多i-1次比较（从后往前找到第一个比待插入的数小的数，最坏情况发生在这个数是所有已经取出的数中最小的一个的时候），在已有数列中给新的数腾出位置需要i-1次赋值操作来实现，还需要两次赋值借助临时变量把新取出的数搬进搬出。也就是说，最坏情况下比较需要n(n-1)/2次，赋值需要n(n-1)/2+2n次。我这么写有点误导人，大家不要以为程序的实现用了两个数组哦，其实一个数组就够了，看看上面的演示就知道了。我只说算法，一般不写如何实现。学算法的都是强人，知道算法了都能写出一个漂亮的代码来。
冒泡排序第i趟排序需要比较n-i次，n-1趟排序总共n(n-1)/2次。给出的序列逆序排列是最坏的情况，这时每一次比较都要进行交换操作。一次交换操作需要3次赋值实现，因此冒泡排序最坏情况下需要赋值3n(n-1)/2次。
按照渐进复杂度理论，忽略所有的常数，三种排序的最坏情况下复杂度都是一样的：O(n^2)。但实际应用中三种排序的效率并不相同。实践证明（政治考试时每道大题都要用这四个字），插入排序是最快的（虽然最坏情况下与选择排序相当甚至更糟），因为每一次插入时寻找插入的位置多数情况只需要与已有数的一部分进行比较（你可能知道这还能二分）。你或许会说冒泡排序也可以在半路上完成，还没有跑到第n-1趟就已经有序。但冒泡排序的交换操作更费时，而插入排序中找到了插入的位置后移动操作只需要用赋值就能完成（你可能知道这还能用move）。本文后面将介绍的一种算法就利用插入排序的这些优势。
我们证明了，三种排序方法在最坏情况下时间复杂度都是O(n^2)。但大家想过吗，这只是最坏情况下的。在很多时候，复杂度没有这么大，因为插入和冒泡在数列已经比较有序的情况下需要的操作远远低于n^2次（最好情况下甚至是线性的）。抛开选择排序不说（因为它的复杂度是“死”的，对于选择排序没有什么“好”的情况），我们下面探讨插入排序和冒泡排序在特定数据和平均情况下的复杂度。
你会发现，如果把插入排序中的移动赋值操作看作是把当前取出的元素与前面取出的且比它大的数逐一交换，那插入排序和冒泡排序对数据的变动其实都是相邻元素的交换操作。下面我们说明，若只能对数列中相邻的数进行交换操作，如何计算使得n个数变得有序最少需要的交换次数。
我们定义逆序对的概念。假设我们要把数列从小到大排序，一个逆序对是指的在原数列中，左边的某个数比右边的大。也就是说，如果找到了某个i和j使得i<j且Ai>Aj，我们就说我们找到了一个逆序对。比如说，数列3,1,4,2中有三个逆序对，而一个已经有序的数列逆序对个数为0。我们发现，交换两个相邻的数最多消除一个逆序对，且冒泡排序（或插入排序）中的一次交换恰好能消除一个逆序对。那么显然，原数列中有多少个逆序对冒泡排序（或插入排序）就需要多少次交换操作，这个操作次数不可能再少。
若给出的n个数中有m个逆序对，插入排序的时间复杂度可以说是O(m+n)的，而冒泡排序不能这么说，因为冒泡排序有很多“无用”的比较（比较后没有交换），这些无用的比较超过了O(m+n)个。从这个意义上说，插入排序仍然更为优秀，因为冒泡排序的复杂度要受到它跑的趟数的制约。一个典型的例子是这样的数列：8, 2, 3, 4, 5, 6, 7, 1。在这样的输入数据下插入排序的优势非常明显，冒泡排序只能哭着喊上天不公。
然而，我们并不想计算排序算法对于某个特定数据的效率。我们真正关心的是，对于所有可能出现的数据，算法的平均复杂度是多少。不用激动了，平均复杂度并不会低于平方。下面证明，两种算法的平均复杂度仍然是O(n^2)的。
我们仅仅证明算法需要的交换次数平均为O(n^2)就足够了。前面已经说过，它们需要的交换次数与逆序对的个数相同。我们将证明，n个数的数列中逆序对个数平均O(n^2)个。
计算的方法是十分巧妙的。如果把给出的数列反过来（从后往前倒过来写），你会发现原来的逆序对现在变成顺序的了，而原来所有的非逆序对现在都成逆序了。正反两个数列的逆序对个数加起来正好就是数列所有数对的个数，它等于n(n-1)/2。于是，平均每个数列有n(n-1)/4个逆序对。忽略常数，逆序对平均个数O(n^2)。
上面的讨论启示我们，要想搞出一个复杂度低于平方级别的排序算法，我们需要想办法能把离得老远的两个数进行操作。
人们想啊想啊想啊，怎么都想不出怎样才能搞出复杂度低于平方的算法。后来，英雄出现了，Donald Shell发明了一种新的算法，我们将证明它的复杂度最坏情况下也没有O(n^2) （似乎有人不喜欢研究正确性和复杂度的证明，我会用实例告诉大家，这些证明是非常有意思的）。他把这种算法叫做Shell增量排序算法（大家常说的希尔排序）。
Shell排序算法依赖一种称之为“排序增量”的数列，不同的增量将导致不同的效率。假如我们对20个数进行排序，使用的增量为1,3,7。那么，我们首先对这20个数进行“7-排序”(7-sortedness)。所谓7-排序，就是按照位置除以7的余数分组进行排序。具体地说，我们将把在1、8、15三个位置上的数进行排序，将第2、9、16个数进行排序，依此类推。这样，对于任意一个数字k，单看A(k), A(k+7), A(k+14), ...这些数是有序的。7-排序后，我们接着又进行一趟3-排序（别忘了我们使用的排序增量为1,3,7）。最后进行1-排序（即普通的排序）后整个Shell算法完成。看看我们的例子：
3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2 <-- 原数列
3 3 2 0 5 1 5 7 4 4 0 6 1 6 8 7 9 9 8 2 <-- 7-排序后
0 0 1 1 2 2 3 3 4 4 5 6 5 6 8 7 7 9 8 9 <-- 3-排序后
0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 <-- 1-排序后（完成）
在每一趟、每一组的排序中我们总是使用插入排序。仔细观察上面的例子你会发现是什么导致了Shell排序的高效。对，每一趟排序将使得数列部分有序，从而使得以后的插入排序很快找到插入位置。我们下面将紧紧围绕这一点来证明Shell排序算法的时间复杂度上界。
只要排序增量的第一个数是1，Shell排序算法就是正确的。但是不同的增量将导致不同的时间复杂度。我们上面例子中的增量(1, 3, 7, 15, 31, ..., 2^k-1)是使用最广泛的增量序列之一，可以证明使用这个增量的时间复杂度为O(n√n)。这个证明很简单，大家可以参看一些其它的资料，我们今天不证明它。今天我们证明，使用增量1, 2, 3, 4, 6, 8, 9, 12, 16, ..., 2^p*3^q，时间复杂度为O(n*(log n)^2)。
很显然，任何一个大于1的正整数都可以表示为2x+3y，其中x和y是非负整数。于是，如果一个数列已经是2-排序的且是3-排序的，那么对于此时数列中的每一个数A(i)，它的左边比它大的只有可能是A(i-1)。A2绝对不可能比A12大，因为10可以表示为两个2和两个3的和，则A2<A4<A6<A9<A12。那么，在这个增量中的1-排序时每个数找插入位置只需要比较一次。一共有n个数，所以1-排序是O(n)的。事实上，这个增量中的2-排序也是O(n)，因为在2-排序之前，这个数列已经是4-排序且6-排序过的，只看数列的奇数项或者偶数项（即单看每一组）的话就又成了刚才的样子。这个增量序列巧妙就巧妙在，如果我们要进行h-排序，那么它一定是2h-排序过且3h-排序过，于是处理每个数A(i)的插入时就只需要和A(i-h)进行比较。这个结论对于最开始几次（h值较大时）的h-排序同样成立，当2h、3h大于n时，按照定义，我们也可以认为数列是2h-排序和3h-排序的，这并不影响上述结论的正确性（你也可以认为h太大以致于排序时每一组里的数字不超过3个，属于常数级）。现在，这个增量中的每一趟排序都是O(n)的，我们只需要数一下一共跑了多少趟。也就是说，我们现在只需要知道小于n的数中有多少个数具有2^p*3^q的形式。要想2^p*3^q不超过n，p的取值最多O(log n)个，q的取值最多也是O(log n)个，两两组合的话共有O(logn*logn)种情况。于是，这样的增量排序需要跑O((log n)^2)趟，每一趟的复杂度O(n)，总的复杂度为O(n*(log n)^2)。早就说过了，证明时间复杂度其实很有意思。
我们自然会想，有没有能使复杂度降到O(nlogn)甚至更低的增量序列。很遗憾，现在没有任何迹象表明存在O(nlogn)的增量排序。但事实上，很多时候Shell排序的实际效率超过了O(nlogn)的排序算法。
后面我们将介绍三种O(nlogn)的排序算法和三种线性时间的排序算法。最后我们将以外部排序和排序网络结束这一章节。
很多人问到我关于转贴的问题。我欢迎除商业目的外任何形式的转贴（论坛、Blog、Wiki、个人网站、PodCast，甚至做成ppt、pdf），但一定要注明出处，最好保留原始链接。我的网站需要点反向链接才能在网络中生存下去，大家也都可以关注并且推广这个Blog。我一直支持cc版权协议，因此发现了文章中的问题或者想要补充什么东西尽管提出来，好让更多的人学习到好东西。我昨天看Blog上原来写的一些东西，居然连着发现了几个错误式子和错别字，好奇大家居然没有提出来。发现了问题真的要告诉我，即使格式有点问题也要说一下，决不能让它那么错着。另外有什么建议或想法也请说一下，我希望听到不同的声音不同的见解，好让我决定这类文章以后的发展方向。
本文被华丽的分割线分为了四段。对于O(nlogn)的排序算法，我们详细介绍归并排序并证明归并排序的时间复杂度，然后简单介绍堆排序，之后给出快速排序的基本思想和复杂度证明。最后我们将证明，O(nlogn)在理论上已经达到了最优。学过OI的人一般都学过这些很基础的东西，大多数OIer们不必看了。为了保持系列文章的完整性，我还是花时间写了一下。
首先考虑一个简单的问题：如何在线性的时间内将两个有序队列合并为一个有序队列（并输出）？
A队列：1 3 5 7 9
B队列：1 2 7 8 9
看上面的例子，AB两个序列都是已经有序的了。在给出数据已经有序的情况下，我们会发现很多神奇的事，比如，我们将要输出的第一个数一定来自于这两个序列各自最前面的那个数。两个数都是1，那么我们随便取出一个（比如A队列的那个1）并输出：
A队列：1 3 5 7 9
B队列：1 2 7 8 9
输出：1
注意，我们取出了一个数，在原数列中删除这个数。删除操作是通过移动队首指针实现的，否则复杂度就高了。
现在，A队列打头的数变成3了，B队列的队首仍然是1。此时，我们再比较3和1哪个大并输出小的那个数：
A队列：1 3 5 7 9
B队列：1 2 7 8 9
输出：1 1
接下来的几步如下：
A队列：1 3 5 7 9 A队列：1 3 5 7 9 A队列：1 3 5 7 9 A队列：1 3 5 7 9
B队列：1 2 7 8 9 ==> B队列：1 2 7 8 9 ==> B队列：1 2 7 8 9 ==> B队列：1 2 7 8 9 ……
输出：1 1 2 输出：1 1 2 3 输出：1 1 2 3 5 输出：1 1 2 3 5 7
我希望你明白了这是怎么做的。这个做法显然是正确的，复杂度显然是线性。
归并排序(Merge Sort)将会用到上面所说的合并操作。给出一个数列，归并排序利用合并操作在O(nlogn)的时间内将数列从小到大排序。归并排序用的是分治(Divide and Conquer)的思想。首先我们把给出的数列平分为左右两段，然后对两段数列分别进行排序，最后用刚才的合并算法把这两段（已经排过序的）数列合并为一个数列。有人会问“对左右两段数列分别排序时用的什么排序”么？答案是：用归并排序。也就是说，我们递归地把每一段数列又分成两段进行上述操作。你不需要关心实际上是怎么操作的，我们的程序代码将递归调用该过程直到数列不能再分（只有一个数）为止。
初看这个算法时有人会误以为时间复杂度相当高。我们下面给出的一个图将用非递归的眼光来看归并排序的实际操作过程，供大家参考。我们可以借助这个图证明，归并排序算法的时间复杂度为O(nlogn)。
[3] [1] [4] [1] [5] [9] [2] [7]
/ / / / / / / /
[1 3] [1 4] [5 9] [2 7]
/ / / /
[1 1 3 4] [2 5 7 9]
/ /
[1 1 2 3 4 5 7 9]
上图中的每一个“ / / ”表示的是上文所述的线性时间合并操作。上图用了4行来图解归并排序。如果有n个数，表示成上图显然需要O(logn)行。每一行的合并操作复杂度总和都是O(n)，那么logn行的总复杂度为O(nlogn)。这相当于用递归树的方法对归并排序的复杂度进行了分析。假设，归并排序的复杂度为T(n)，T(n)由两个T(n/2)和一个关于n的线性时间组成，那么T(n)=2*T(n/2)+O(n)。不断展开这个式子我们可以同样可以得到T(n)=O(nlogn)的结论，你可以自己试试。如果你能在线性的时间里把分别计算出的两组不同数据的结果合并在一起，根据T(n)=2*T(n/2)+O(n)=O(nlogn)，那么我们就可以构造O(nlogn)的分治算法。这个结论后面经常用。我们将在计算几何部分举一大堆类似的例子。
如果你第一次见到这么诡异的算法，你可能会对这个感兴趣。分治是递归的一种应用。这是我们第一次接触递归运算。下面说的快速排序也是用的递归的思想。递归程序的复杂度分析通常和上面一样，主定理(Master Theory)可以简化这个分析过程。主定理和本文内容离得太远，我们以后也不会用它，因此我们不介绍它，大家可以自己去查。有个名词在这里的话找学习资料将变得非常容易，我最怕的就是一个东西不知道叫什么名字，半天找不到资料。
归并排序有一个有趣的副产品。利用归并排序能够在O(nlogn)的时间里计算出给定序列里逆序对的个数。你可以用任何一种平衡二叉树来完成这个操作，但用归并排序统计逆序对更方便。我们讨论逆序对一般是说的一个排列中的逆序对，因此这里我们假设所有数不相同。假如我们想要数1, 6, 3, 2, 5, 4中有多少个逆序对，我们首先把这个数列分为左右两段。那么一个逆序对只可能有三种情况：两个数都在左边，两个数都在右边，一个在左一个在右。在左右两段分别处理完后，线性合并的过程中我们可以顺便算出所有第三种情况的逆序对有多少个。换句话说，我们能在线性的时间里统计出A队列的某个数比B队列的某个数大有多少种情况。
A队列：1 3 6 A队列：1 3 6 A队列：1 3 6 A队列：1 3 6 A队列：1 3 6
B队列：2 4 5 ==> B队列：2 4 5 ==> B队列：2 4 5 ==> B队列：2 4 5 ==> B队列：2 4 5 ……
输出： 输出：1 输出：1 2 输出：1 2 3 输出：1 2 3 4
每一次从B队列取出一个数时，我们就知道了在A队列中有多少个数比B队列的这个数大，它等于A队列现在还剩的数的个数。比如，当我们从B队列中取出2时，我们同时知道了A队列的3和6两个数比2大。在合并操作中我们不断更新A队列中还剩几个数，在每次从B队列中取出一个数时把当前A队列剩的数目加进最终答案里。这样我们算出了所有“大的数在前一半，小的数在后一半”的情况，其余情况下的逆序对在这之前已经被递归地算过了。
============================华丽的分割线============================
堆排序(Heap Sort)利用了堆(Heap)这种数据结构（什么是堆？）。堆的插入操作是平均常数的，而删除一个根节点需要花费O(log n)的时间。因此，完成堆排序需要线性时间建立堆（把所有元素依次插入一个堆），然后用总共O(nlogn)的时间不断取出最小的那个数。只要堆会搞，堆排序就会搞。堆在那篇日志里有详细的说明，因此这里不重复说了。
============================华丽的分割线============================
快速排序(Quick Sort)也应用了递归的思想。我们想要把给定序列分成两段，并对这两段分别进行排序。一种不错的想法是，选取一个数作为“关键字”，并把其它数分割为两部分，把所有小于关键字的数都放在关键字的左边，大于关键字的都放在右边，然后递归地对左边和右边进行排序。把该区间内的所有数依次与关键字比较，我们就可以在线性的时间里完成分割的操作。完成分割操作有很多有技巧性的实现方法，比如最常用的一种是定义两个指针，一个从前往后找找到比关键字大的，一个从后往前找到比关键字小的，然后两个指针对应的元素交换位置并继续移动指针重复刚才的过程。这只是大致的方法，具体的实现还有很多细节问题。快速排序是我们最常用的代码之一，网上的快速排序代码五花八门，各种语言，各种风格的都有。大家可以随便找一个来看看，我说过了我们讲算法但不讲如何实现。NOIp很简单，很多人NOIp前就背了一个快速排序代码就上战场了。当时我把快速排序背完了，抓紧时间还顺便背了一下历史，免得晚上听写又不及格。
不像归并排序，快速排序的时间复杂度很难计算。我们可以看到，归并排序的复杂度最坏情况下也是O(nlogn)的，而快速排序的最坏情况是O(n^2)的。如果每一次选的关键字都是当前区间里最大（或最小）的数，那么这样将使得每一次的规模只减小一个数，这和插入排序、选择排序等平方级排序没有区别。这种情况不是不可能发生。如果你每次选择关键字都是选择的该区间的第一个数，而给你的数据恰好又是已经有序的，那你的快速排序就完蛋了。显然，最好情况是每一次选的数正好就是中位数，这将把该区间平分为两段，复杂度和前面讨论的归并排序一模一样。根据这一点，快速排序有一些常用的优化。比如，我们经常从数列中随机取一个数当作是关键字（而不是每次总是取固定位置上的数），从而尽可能避免某些特殊的数据所导致的低效。更好的做法是随机取三个数并选择这三个数的中位数作为关键字。而对三个数的随机取值反而将花费更多的时间，因此我们的这三个数可以分别取数列的头一个数、末一个数和正中间那个数。另外，当递归到了一定深度发现当前区间里的数只有几个或十几个时，继续递归下去反而费时，不如返回插入排序后的结果。这种方法同时避免了当数字太少时递归操作出错的可能。
下面我们证明，快速排序算法的平均复杂度为O(nlogn)。不同的书上有不同的解释方法，这里我选用算法导论上的讲法。它更有技巧性一些，更有趣一些，需要转几个弯才能想明白。
看一看快速排序的代码。正如我们提到过的那种分割方法，程序在经过若干次与关键字的比较后才进行一次交换，因此比较的次数比交换次数更多。我们通过证明一次快速排序中元素之间的比较次数平均为O(nlogn)来说明快速排序算法的平均复杂度。证明的关键在于，我们需要算出某两个元素在整个算法过程中进行过比较的概率。
我们举一个例子。假如给出了1到10这10个数，第一次选择关键字7将它们分成了{1,2,3,4,5,6}和{8,9,10}两部分，递归左边时我们选择了3作为关键字，使得左部分又被分割为{1,2}和{4,5,6}。我们看到，数字7与其它所有数都比较过一次，这样才能实现分割操作。同样地，1到6这6个数都需要与3进行一次比较（除了它本身之外）。然而，3和9决不可能相互比较过，2和6也不可能进行过比较，因为第一次出现在3和9，2和6之间的关键字把它们分割开了。也就是说，两个数A(i)和A(j)比较过，当且仅当第一个满足A(i)<=x<=A(j)的关键字x恰好就是A(i)或A(j) （假设A(i)比A(j)小）。我们称排序后第i小的数为Z(i)，假设i<j，那么第一次出现在Z(i)和Z(j)之间的关键字恰好就是Z(i)或Z(j)的概率为2/(j-i+1)，这是因为当Z(i)和Z(j)之间还不曾有过关键字时，Z(i)和Z(j)处于同一个待分割的区间，不管这个区间有多大，不管递归到哪里了，关键字的选择总是随机的。我们得到，Z(i)和Z(j)在一次快速排序中曾经比较过的概率为2/(j-i+1)。
现在有四个数，2,3,5,7。排序时，相邻的两个数肯定都被比较过，2和5、3和7都有2/3的概率被比较过，2和7之间被比较过有2/4的可能。也就是说，如果对这四个数做12次快速排序，那么2和3、3和5、5和7之间一共比较了12*3=36次，2和5、3和7之间总共比较了8*2=16次，2和7之间平均比较了6次。那么，12次排序中总的比较次数期望值为36+16+6=58。我们可以计算出单次的快速排序平均比较了多少次：58/12=29/6。其实，它就等于6项概率之和，1+1+1+2/3+2/3+2/4=29/6。这其实是与期望值相关的一个公式。
同样地，如果有n个数，那么快速排序平均需要的比较次数可以写成下面的式子。令k=j-i，我们能够最终得到比较次数的期望值为O(nlogn)。
这里用到了一个知识：1+1/2+1/3+...+1/n与log n增长速度相同，即Σ(1/n)=Θ(log n)。它的证明放在本文的最后。
在三种O(nlogn)的排序算法中，快速排序的理论复杂度最不理想，除了它以外今天说的另外两种算法都是以最坏情况O(nlogn)的复杂度进行排序。但实践上看快速排序效率最高（不然为啥叫快速排序呢），原因在于快速排序的代码比其它同复杂度的算法更简洁，常数时间更小。
快速排序也有一个有趣的副产品：快速选择给出的一些数中第k小的数。一种简单的方法是使用上述任一种O(nlogn)的算法对这些数进行排序并返回排序后数组的第k个元素。快速选择(Quick Select)算法可以在平均O(n)的时间完成这一操作。它的最坏情况同快速排序一样，也是O(n^2)。在每一次分割后，我们都可以知道比关键字小的数有多少个，从而确定了关键字在所有数中是第几小的。我们假设关键字是第m小。如果k=m，那么我们就找到了答案——第k小元素即该关键字。否则，我们递归地计算左边或者右边：当k<m时，我们递归地寻找左边的元素中第k小的；当k>m时，我们递归地寻找右边的元素中第k-m小的数。由于我们不考虑所有的数的顺序，只需要递归其中的一边，因此复杂度大大降低。复杂度平均线性，我们不再具体证了。
还有一种算法可以在最坏O(n)的时间里找出第k小元素。那是我见过的所有算法中最没有实用价值的算法。那个O(n)只有理论价值。
============================华丽的分割线============================
我们前面证明过，仅仅依靠交换相邻元素的操作，复杂度只能达到O(n^2)。于是，人们尝试交换距离更远的元素。当人们发现O(nlogn)的排序算法似乎已经是极限的时候，又是什么制约了复杂度的下界呢？我们将要讨论的是更底层的东西。我们仍然假设所有的数都不相等。
我们总是不断在数与数之间进行比较。你可以试试，只用4次比较绝对不可能给4个数排出顺序。每多进行一次比较我们就又多知道了一个大小关系，从4次比较中一共可以获知4个大小关系。4个大小关系共有2^4=16种组合方式，而4个数的顺序一共有4!=24种。也就是说，4次比较可能出现的结果数目不足以区分24种可能的顺序。更一般地，给你n个数叫你排序，可能的答案共有n!个，k次比较只能区分2^k种可能，于是只有2^k>=n!时才有可能排出顺序。等号两边取对数，于是，给n个数排序至少需要log2(n!)次。注意，我们并没有说明一定能通过log2(n!)次比较排出顺序。虽然2^5=32超过了4!，但这不足以说明5次比较一定足够。如何用5次比较确定4个数的大小关系还需要进一步研究。第一次例外发生在n=12的时候，虽然2^29>12!，但现已证明给12个数排序最少需要30次比较。我们可以证明log(n!)的增长速度与nlogn相同，即log(n!)=Θ(nlogn)。这是排序所需要的最少的比较次数，它给出了排序复杂度的一个下界。log(n!)=Θ(nlogn)的证明也附在本文最后。
这篇日志的第三题中证明log2(N)是最优时用到了几乎相同的方法。那种“用天平称出重量不同的那个球至少要称几次”一类题目也可以用这种方法来解决。事实上，这里有一整套的理论，它叫做信息论。信息论是由香农(Shannon)提出的。他用对数来表示信息量，用熵来表示可能的情况的随机性，通过运算可以知道你目前得到的信息能够怎样影响最终结果的确定。如果我们的信息量是以2为底的，那信息论就变成信息学了。从根本上说，计算机的一切信息就是以2为底的信息量(bits=binary digits)，因此我们常说香农是数字通信之父。信息论和热力学关系密切，比如熵的概念是直接从热力学的熵定义引申过来的。和这个有关的东西已经严重偏题了，这里不说了，有兴趣可以去看《信息论与编码理论》。我对这个也很有兴趣，半懂不懂的，很想了解更多的东西，有兴趣的同志不妨加入讨论。物理学真的很神奇，利用物理学可以解决很多纯数学问题，我有时间的话可以举一些例子。我他妈的为啥要选文科呢。
后面将介绍的三种排序是线性时间复杂度，因为，它们排序时根本不是通过互相比较来确定大小关系的。
附1：Σ(1/n)=Θ(log n)的证明
首先我们证明，Σ(1/n)=O(log n)。在式子1+1/2+1/3+1/4+1/5+...中，我们把1/3变成1/2，使得两个1/2加起来凑成一个1；再把1/5,1/6和1/7全部变成1/4，这样四个1/4加起来又是一个1。我们把所有1/2^k的后面2^k-1项全部扩大为1/2^k，使得这2^k个分式加起来是一个1。现在，1+1/2+...+1/n里面产生了几个1呢？我们只需要看小于n的数有多少个2的幂即可。显然，经过数的扩大后原式各项总和为log n。O(logn)是Σ(1/n)的复杂度上界。
然后我们证明，Σ(1/n)=Ω(log n)。在式子1+1/2+1/3+1/4+1/5+...中，我们把1/3变成1/4，使得两个1/4加起来凑成一个1/2；再把1/5,1/6和1/7全部变成1/8，这样四个1/8加起来又是一个1/2。我们把所有1/2^k的前面2^k-1项全部缩小为1/2^k，使得这2^k个分式加起来是一个1/2。现在，1+1/2+...+1/n里面产生了几个1/2呢？我们只需要看小于n的数有多少个2的幂即可。显然，经过数的缩小后原式各项总和为1/2*logn。Ω(logn)是Σ(1/n)的复杂度下界。
附2：log(n!)=Θ(nlogn)的证明
首先我们证明，log(n!)=O(nlogn)。显然n!<n^n，两边取对数我们得到log(n!)<log(n^n)，而log(n^n)就等于nlogn。因此，O(nlogn)是log(n!)的复杂度上界。
然后我们证明，log(n!)=Ω(nlogn)。n!=n(n-1)(n-2)(n-3)....1，把前面一半的因子全部缩小到n/2，后面一半因子全部舍去，显然有n!>(n/2)^(n/2)。两边取对数，log(n!)>(n/2)log(n/2)，后者即Ω(nlogn)。因此，Ω(nlogn)是log(n!)的复杂度下界。
那么，有什么方法可以不用比较就能排出顺序呢？借助Hash表的思想，多数人都能想出这样一种排序算法来。
我们假设给出的数字都在一定范围中，那么我们就可以开一个范围相同的数组，记录这个数字是否出现过。由于数字有可能有重复，因此Hash表的概念需要扩展，我们需要把数组类型改成整型，用来表示每个数出现的次数。
看这样一个例子，假如我们要对数列3 1 4 1 5 9 2 6 5 3 5 9进行排序。由于给定数字每一个都小于10，因此我们开一个0到9的整型数组T[i]，记录每一个数出现了几次。读到一个数字x，就把对应的T[x]加一。
A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9
+---+---+---+---+---+---+---+---+---+---+
数字 i： | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
+---+---+---+---+---+---+---+---+---+---+
出现次数T[i]： | 0 | 2 | 1 | 2 | 1 | 3 | 1 | 0 | 0 | 2 |
+---+---+---+---+---+---+---+---+---+---+
最后，我们用一个指针从前往后扫描一遍，按照次序输出0到9，每个数出现了几次就输出几个。假如给定的数是n个大小不超过m的自然数，显然这个算法的复杂度是O(m+n)的。
我曾经以为，这就是线性时间排序了。后来我发现我错了。再后来，我发现我曾犯的错误是一个普遍的错误。很多人都以为上面的这个算法就是传说中的计数排序。问题出在哪里了？为什么它不是线性时间的排序算法？原因是，这个算法根本不是排序算法，它根本没有对原数据进行排序。
问题一：为什么说上述算法没有对数据进行排序？
STOP! You should think for a while.
我们班有很多MM。和身高相差太远的MM在一起肯定很别扭，接个吻都要弯腰才行（小猫矮死了）。为此，我希望给我们班的MM的身高排序。我们班MM的身高，再离谱也没有超过2米的，这很适合用我们刚才的算法。我们在黑板上画一个100到200的数组，MM依次自曝身高，我负责画“正”字统计人数。统计出来了，从小到大依次为141, 143, 143, 147, 152, 153, ...。这算哪门子排序？就一排数字对我有什么用，我要知道的是哪个MM有多高。我们仅仅把元素的属性值从小到大列了出来，但我们没有对元素本身进行排序。也就是说，我们需要知道输出结果的每个数值对应原数据的哪一个元素。下文提到的“排序算法的稳定性”也和属性值与实际元素的区别有关。
问题二：怎样将线性时间排序后的输出结果还原为原数据中的元素？
STOP! You should think for a while.
同样借助Hash表的思想，我们立即想到了类似于开散列的方法。我们用链表把属性值相同的元素串起来，挂在对应的T[i]上。每次读到一个数，在增加T[i]的同时我们把这个元素放进T[i]延伸出去的链表里。这样，输出结果时我们可以方便地获得原数据中的所有属性值为i的元素。
A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9
+---+---+---+---+---+---+---+---+---+---+
数字 i： | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
+---+---+---+---+---+---+---+---+---+---+
出现次数T[i]： | 0 | 2 | 1 | 2 | 1 | 3 | 1 | 0 | 0 | 2 |
+---+o--+-o-+-o-+-o-+-o-+--o+---+---+-o-+
| | | | | | |
+--+ +-+ | | +-+ +---+ |
| | A[1] | | | A[6]
A[2] A[7] | A[3] A[5] A[8] |
| | | A[12]
A[4] A[10] A[9]
|
A[11]
形象地说，我们在地上摆10个桶，每个桶编一个号，然后把数据分门别类放在自己所属的桶里。这种排序算法叫做桶式排序(Bucket Sort)。本文最后你将看到桶式排序的另一个用途。
链表写起来比较麻烦，一般我们不使用它。我们有更简单的方法。
问题三：同样是输出元素本身，你能想出不用链表的其它算法么？
STOP! You should think for a while.
A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9
+---+---+---+---+---+---+---+---+---+---+
数字 i： | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
+---+---+---+---+---+---+---+---+---+---+
出现次数T[i]： | 0 | 2 | 1 | 2 | 1 | 3 | 1 | 0 | 0 | 2 |
+---+---+---+---+---+---+---+---+---+---+
修改后的T[i]： | 0 | 2 | 3 | 5 | 6 | 9 | 10| 10| 10| 12|
+---+---+---+---+---+---+---+---+---+---+
所有数都读入后，我们修改T[i]数组的值，使得T[i]表示数字i可能的排名的最大值。比如，1最差排名第二，3最远可以排到第五。T数组的最后一个数应该等于输入数据的数字个数。修改T数组的操作可以用一次线性的扫描累加完成。
我们还需要准备一个输出数组。然后，我们从后往前扫描A数组，依照T数组的指示依次把原数据的元素直接放到输出数组中，同时T[i]的值减一。之所以从后往前扫描A数组，是因为这样输出结果才是稳定的。我们说一个排序算法是稳定的(Stable)，当算法满足这样的性质：属性值相同的元素，排序后前后位置不变，本来在前面的现在仍然在前面。不要觉得排序算法是否具有稳定性似乎关系不大，排序的稳定性在下文的某个问题中将变得非常重要。你可以倒回去看看前面说的七种排序算法哪些是稳定的。
例子中，A数组最后一个数9所对应的T[9]=12，我们直接把9放在待输出序列中的第12个位置，然后T[9]变成11（这样下一次再出现9时就应该放在第11位）。
A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9 <--
T[i]= 0, 2, 3, 5, 6, 9, 10, 10, 10, 11
Ans = _ _ _ _ _ _ _ _ _ _ _ 9
接下来的几步如下：
A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 <--
T[i]= 0, 2, 3, 5, 6, 8, 10, 10, 10, 11
Ans = _ _ _ _ _ _ _ _ 5 _ _ 9
A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5, 3 <--
T[i]= 0, 2, 3, 4, 6, 8, 10, 10, 10, 11
Ans = _ _ _ _ 3 _ _ _ 5 _ _ 9
A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5 <--
T[i]= 0, 2, 3, 4, 6, 7, 10, 10, 10, 11
Ans = _ _ _ _ 3 _ _ 5 5 _ _ 9
这种算法叫做计数排序(Counting Sort)。正确性和复杂度都是显然的。
问题四：给定数的数据范围大了该怎么办？
STOP! You should think for a while.
前面的算法只有在数据的范围不大时才可行，如果给定的数在长整范围内的话，这个算法是不可行的，因为你开不下这么大的数组。Radix排序(Radix Sort)解决了这个难题。
昨天我没事翻了一下初中（9班）时的同学录，回忆了一下过去。我把比较感兴趣的MM的生日列在下面（绝对真实）。如果列表中的哪个MM有幸看到了这篇日志（几乎不可能），左边的Support栏有我的电子联系方式，我想知道你们怎么样了。排名不分先后。
- 19880818
- 19880816
- 19890426
- 19880405
- 19890125
- 19881004
- 19881209
- 19890126
- 19890228
这就是我的数据了。现在，我要给这些数排序。假如我的电脑只能开出0..99的数组，那计数排序算法最多对两位数进行排序。我就把每个八位数两位两位地分成四段（图1），分别进行四次计数排序。地球人都知道月份相同时应该看哪一日，因此我们看月份的大小时应该事先保证日已经有序。换句话说，我们先对“最不重要”的部分进行排序。我们先对所有数的最后两位进行一次计数排序（图2）。注意观察1月26号的MM和4月26号的MM，本次排序中它们的属性值相同，由于计数排序是稳定的，因此4月份那个排完后依然在1月份那个的前头。接下来我们对百位和千位进行排序（图3）。你可以看到两个26日的MM在这一次排序中分出了大小，而月份相同的MM依然保持日数有序（因为计数排序是稳定的）。最后我们对年份排序（图4），完成整个算法。大家都是跨世纪的好儿童，因此没有图5了。
这种算法显然是正确的。它的复杂度一般写成O(d*(n+m))，其中n表示n个数，m是我开的数组大小（本例中m=100），d是一个常数因子（本例中d=4）。我们认为它也是线性的。
问题五：这样的排序方法还有什么致命的缺陷？
STOP! You should think for a while.
即使数据有30位，我们也可以用d=5或6的Radix算法进行排序。但，要是给定的数据有无穷多位怎么办？有人说，这可能么。这是可能的，比如给定的数据是小数（更准确地说，实数）。基于比较的排序可以区分355/113和π哪个大，但你不知道Radix排序需要精确到哪一位。这下惨了，实数的出现把貌似高科技的线性时间排序打回了农业时代。这时，桶排序再度出山，挽救了线性时间排序悲惨的命运。
问题六：如何对实数进行线性时间排序？
STOP! You should think for a while.
我们把问题简化一下，给出的所有数都是0到1之间的小数。如果不是，也可以把所有数同时除以一个大整数从而转化为这种形式。我们依然设立若干个桶，比如，以小数点后面一位数为依据对所有数进行划分。我们仍然用链表把同一类的数串在一起，不同的是，每一个链表都是有序的。也就是说，每一次读到一个新的数都要进行一次插入排序。看我们的例子：
A[]= 0.12345, 0.111, 0.618, 0.9, 0.99999
+---+---+---+---+---+---+---+---+---+---+
十分位： | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
+---+-o-+---+---+---+---+-o-+---+---+-o-+
| | |
A[2]=0.111 A[3]=0.618 A[4]=0.9
| |
A[1]=0.12345 A[5]=0.99999
假如再下一个读入的数是0.122222，这个数需要插入到十分位为1的那个链表里适当的位置。我们需要遍历该链表直到找到第一个比0.122222大的数，在例子中则应该插入到链表中A[2]和A[1]之间。最后，我们按顺序遍历所有链表，依次输出每个链表中的每个数。
这个算法显然是正确的，但复杂度显然不是线性。事实上，这种算法最坏情况下是O(n^2)的，因为当所有数的十分位都相同时算法就是一个插入排序。和原来一样，我们下面要计算算法的平均时间复杂度，我们希望这种算法的平均复杂度是线性的。
这次算平均复杂度我们用最笨的办法。我们将算出所有可能出现的情况的总时间复杂度，除以总的情况数，得到平均的复杂度是多少。
每个数都可能属于10个桶中的一个，n个数总的情况有10^n种。这个值是我们庞大的算式的分母部分。如果一个桶里有K个元素，那么只与这个桶有关的操作有O(K^2)次，它就是一次插入排序的操作次数。下面计算，在10^n种情况中，K0=1有多少种情况。K0=1表示，n个数中只有一个数在0号桶，其余n-1个数的十分位就只能在1到9中选择。那么K0=1的情况有C(n,1)*9^(n-1)，而每个K0=1的情况在0号桶中将产生1^2的复杂度。类似地，Ki=p的情况数为C(n,p)*9^(n-p)，复杂度总计为C(n,p)*9^(n-p)*p^2。枚举所有K的下标和p值，累加起来，这个算式大家应该能写出来了，但是这个……怎么算啊。别怕，我们是搞计算机的，拿出点和MO不一样的东西来。于是，Mathematica 5.0隆重登场，我做数学作业全靠它。它将帮我们化简这个复杂的式子。
我们遗憾地发现，虽然常数因子很小（只有0.1），但算法的平均复杂度仍然是平方的。等一下，1/10的那个10是我们桶的个数吗？那么我们为什么不把桶的个数弄大点？我们干脆用m来表示桶的个数，重新计算一次：
化简出来，操作次数为O(n+n^2/m)。发现了么，如果m=Θ(n)的话，平均复杂度就变成了O(n)。也就是说，当桶的个数等于输入数据的个数时，算法是平均线性的。
我们将在Hash表开散列的介绍中重新提到这个结论。
且慢，还有一个问题。10个桶以十分位的数字归类，那么n个桶用什么方法来分类呢？注意，分类的方法需要满足，一，一个数分到每个桶里的概率相同（这样才有我们上面的结论）；二，所有桶里容纳元素的范围必须是连续的。根据这两个条件，我们有办法把所有数恰好分为n类。我们的输入数据不是都在0到1之间么？只需要看这些数乘以n的整数部分是多少就行了，读到一个数后乘以n取整得几就插入到几号桶里。这本质上相当于把区间[0,1)平均分成n份。
问题七：有没有复杂度低于线性的排序算法
STOP! You should think for a while.
我们从O(n^2)走向O(nlogn)，又从O(nlogn)走向线性，每一次我们都讨论了复杂度下限的问题，根据讨论的结果提出了更优的算法。这次总算不行了，不可能有比线性还快的算法了，因为——你读入、输出数据至少就需要线性的时间。排序算法之旅在线性时间复杂度这一站终止了，所有十种排序算法到这里介绍完毕了。
文章有越写越长的趋势了，我检查起来也越来越累了。我又看了三遍，应该没问题了。群众的眼睛是雪亮的，恳请大家帮我找错。
Matrix67原创
