看一看快速排序的代码。正如我们提到过的那种分割方法，程序在经过若干次与关键字的比较后才进行一次交换，因此比较的次数比交换
次数更多。我们通过证明一 次快速排序中元素之间的比较次数平均为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 概率为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 中第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! 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!)的复杂度下界。转自：Matrix67 那么，有什么方法可以不用比较就能排出顺序呢？借助Hash表的思想，多数人都能想出这样一种排序算法来。 我们假设给出的数字都在一定范围中，那么我们就可以开一个范围相同的数组，记录这个数字是否出现过。由于数字有可能有重复，因此 Hash表的概念需要扩展，我们需要把数组类型改成整型，用来表示每个数出现的次数。 看这样一个例子，假如我们要对数列3 1 4 1 5 9 2 6 5 35 9进行排序。由于给定数字每一个都小于10，因此我们开一个0到9的整型数 组T，记录每一个数出现了几次。读到一个数字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： | 0 | 2 | 1 | 2 | 1 | 3 | 1 | 0 |0 | 2 | +---+---+---+---+---+---+---+---+---+---+ 最后，我们用一个指针从前往后扫描一遍，按照次序输出0到9，每个数出现了几次就输出几个。假如给定的数是n个大小不超过m的自然数 ，显然这个算法的复杂度是O(m+n)的。 我曾经以为，这就是线性时间排序了。后来我发现我错了。再后来，我发现我曾犯的错误是一个普遍的错误。很多人都以为上面的这个算 法就是传说中的计数排序。 问题出在哪里了？为什么它不是线性时间的排序算法？原因是，这个算法根本