漫话进位制

2007 年 5 月 20 日 / 18 条评论

    人有十个手指，用手指的伸屈来计数非常方便。但一旦对象的数目超过10个了，手指头就不够用了。当然，有人会想到还有脚趾头。搬弄脚趾头是不现实的，数手指头只需要站着比划一下就可以了，数脚趾头还需要坐下来慢慢研究。一种好的方法是每次数完了十个指头后在什么地方做一个标记，比如在地上放一个木棒。人们可以把这根木棒想像成一个“大指头”，它相当于十个指头。这样，我有37个MM就被表示成了地上3个木棒加上我7个手指头。哈哈，你的MM数只有两根木棒加4个手指头，于是我的MM比你的多。久而久之，人们就只接受0到9这十个数字了，再大的数就用几个数字合起来表示。这种“满十进一”的数字系统就叫做十进位制。
    如果人只有八个手指头又会怎样呢？那我们现在很可能正在使用八进制，数学发展起来后我们最终只接受八个数字，而大于8的数字就用更高一级的计量单位表示。代表这八个数字的很可能是些星际之门里的怪符号，这里为了便于叙述，我们仍然使用阿拉伯数字的0到7来表示。于是，人类数数的方式将变为：0,1,2,3,4,5,6,7,10,11,12,13,14,15,16,17,20,…。这里，数字8被记作10，数字64则用100代替。在这个数学世界里，6+5=13，因为6+1得到的数已经是一位数中最大的了，再加的话只能“进一位”了。“满八进一”将成为数学运算的基本法则。
    如果人有12根手指，12进制将成为更难想像的事。在12进制中，人类会把10和11直接想成是一个“数字”。研究的进位制大于10时，大于9的数字我们习惯上用大写字母ABC来表示。这样，自然数序列里将多出两个符号A和B来，数数的方式变为…,8,9,A,B,10,11,12,…。

我们自然会想，人类生活中究竟有没有其它的进位制呢？当然有。比如，时间和角度就是60进位制，60秒=1分。还有更怪的，计算机的储存容量单位是1024进制的，1MB=1024KB。当然，这也是有原因的。我们在研究几何时常常需要用到1/2，1/3，1/4或者1/6，我们希望这些分数在角度进制下恰好都是整数以便于运算。于是，角度的进位制就变成了60。为什么时间也是60进位制呢？因为时间和角度密切相关，你看看你的手表就知道了（别告诉我你的手表是数字型的）。为什么钟和手表又要用圆形表盘的方式来表示时间呢？其实人自古以来计算时间都是用的圆形盘面，因为地球绕太阳旋转和地球的自转使得时间具有了周期性。
计算机使用二进制，因为计算机元件只有两种状态（开和关，或者说通电和断电），因此计算机只认0和1两个数字。1024是2的幂，又比较接近1000符合人的习惯，因此把1024当成了计算机容量的进位制。

前段时间有人在OIBH上问，为什么纸币的面值都是1*10^n、2*10^n、5*10^n呢。有人回答说这样的货币系统可以使得某种贪心方法正确。确实有这个结论，这样的货币系统使得解决“凑钱和找零时最少使用多少张纸币”这一问题的贪心算法（不断拿最大面额的纸币）是正确。但用这一点来解释我们的问题显然是可笑的，人们首先考虑的并不是如何方便地使用最少纸币，而是如何方便地得到总面额。一个只有1元纸币和7元纸币的货币系统同样满足贪心性质，但显然傻子才会设计出这种别扭的货币系统来。因此，我的回答是“纸币的面值取10的约数，这样的话凑钱和找零最方便”。但是，有人会问，要是我们使用的进位制不是10怎么办？换句话说，如果我们使用的是23进位制，除1和本身外没有其它约数的话，又该怎样设置货币系统呢。答案非常出人意料，如果我们使用的是23进位制的话，我们很可能根本发展不出数学这门学科来。10=1+2+3+4，是前四个正整数的和；10又是2和5的积；这样的进位制非常适合数学的发展。同样地，6=1+2+3，6=2*3，因此可能正在使用六进制的昆虫们很容易发展出数学来（六足动物的数学非常强，不是有人发现了蜜蜂蜂巢的六边形样式设计是最科学的么）。大家看过《计算机中的上帝》(Calculating God)吗？那里面构造了这样一种生物：他有23根手指。这种别扭的数字最多只能让人联想到乔丹和染色体，除此之外没有任何特性。这给这种生物的数学发展带来不可逾越的困难。而事实上，这种生物恰好又没有发展数学的必要性。他就好像人类一样，对较小的物体个数具有直接感知的能力。人类可以直接感知的物体数量一般不超过6。也就是说，如果你眼前有3个，或者5个东西，你不需要数，看一眼就知道有多少个；但当你眼前出现的物体数目达到7个或者8个时，你就必须要数一数才知道个数了。而我们所说的生物面对的物体数目多达46个时仍然可以一眼分辨出多少来，数目超过46后就统称为“很多”了。直接感知数目达到50甚至60多的生物个体就扮演着该种族中的僧侣角色。46这个数字对于种族的生存已经完全足够了，他们在组建部落时总会保证部落的个体数不超过这个数字。因此，这种生物不需要数数的能力，他们也就无须发展数学了。他们不知道30加30等于多少，从某种意义上说他们甚至不知道一加一等于几，因为他们头脑中根本没有数字这个概念。作为一种补偿，他们对事物的感知能力相当敏锐。他们甚至直接凭直觉感知到了相对论，因为他们的思维不受演绎逻辑的束缚。

下文将介绍两套进制转换的方法，然后介绍这两套方法在小数转换上的应用。更多的进位制相关应用你可以在文后的习题部分中体会到。

    在讲进位制时，大多数教材会教大家二进制和十进制如何互换。今天我就偏不这样讲，我要和那些教材讲得一样了我还不如不写今天这些东西。二进制虽然常用，但比较特殊，很可能会了二进制但仍然不会其它进制；我们今天当一回蜜蜂，看看六进制和十进制怎么互相转换。学会这个后，任意进制间的转换你就应该都会了。
    说起进位制时往往要回到最根本的一些计数方法上。这篇日志是我第237篇日志。数字“237”表示两个百，加上三个十，加上七个单位一。我们把它们分别叫百位、十位和个位，同一个数字在不同数位上表示的实际数量不同。用一个式子表示上面的意思就是，237=2*100+3*10+7。这就是进位制的实际意义。
    现在，假如我是一只勤劳的蜜蜂。我写237篇日志是肯定不可能的了，因为我的数学世界里根本没有7这个数字。那就说我写了235篇日志吧。结合前面所说的东西，“十位”上的数表示有多少个6，“百位”上的数表示有多少个36（后面提到的十位、百位打引号表明这不是十进制中的“十”和“百”）。于是，六进制下的235就应该等于2*6^2+3*6+5。这个算式你用什么进制算出答案就相当于把六进制中的235转换为了什么进制。不过你要把这个式子当成别的进制算是不大可能的，算之前你估计得重新背一遍乘法口诀表（注意我为什么不说是“九九”乘法口诀表）。这就是我们为什么一般只研究十进制与其它进制互换的原因。我们用熟悉的十进制进行计算，得出2*6^2+3*6+5=72+18+5=95。这是按定义进行进制转换的方法。六进制的235等于十进制的95，我们记作(
235)6=(95)10。那个6和10是下标，应该像H2O的2一样小小地写在下面。我就懒得排版了，反正转贴个几次就成Plain Text了。
    下面的任务是，考虑怎么把(95)10变回(235)6。使用六进制计算13*10+5可以得到235（十位上的9相当于六进制中的13），但我们说过六进制计算很麻烦。下面我们给出一种把十进制转换为六进制的方法，仔细思考你会发现这种方法显然是正确的。我们把所有6的幂从小到大写出来：1,6,36,216,…。216远远超过95了，因此95的六进制不可能是四位数。95里面有两个36，因此在最高位上写个“2”。去掉两个36，95里只剩23。23里有三个6，数字3将填写在第二位上，去掉这三个6最后所剩的5留给最末位。换句话说，我们不断寻找最大的x使得6^x不超过当前数，当前数减去6^x并在右起第x+1位上加一。这事实上是前面六进制转十进制的逆过程。
    上面的进制互换方法是一套方法，这是我们所介绍的第一套方法。这套方法的特点是正确性很显然，但是计算比较复杂，又费马达又费电。我们需要一个计算更方便的进制转换方法。下面介绍的就是进制转换的第二套方案。

再一次回到一个很基础的问题：在十进制中，为什么乘以10相当于在数的末尾加一个0？我们同样会联想到位运算：为什么二进制左移一位（末尾加一个0）相当于乘以2？事实上，这个结论普遍存在于所有进位制中：k进制数的末尾加个0，相当于该数乘以k。证明方法非常简单，乘以一个k就相当于进位制展开式的每个指数都加一，也就相当于所有数字左移一位。六进制235=2*6^2+3*6+5，乘以6的话式子将变为2*6^3+3*6^2+5*6，也即2350。利用这个性质，六进制235可以很快转为十进制：235相当于2后面添0，加上3，再添一个0，再加上5，写为算式即(2*6+3)*6+5=95。把(2*6+3)*6+5展开来，得到的式子和前面的那种计算方法(2*6^2+3*6+5)一模一样，但这里的计算方式更简便一些。如果写成程序，六进制字符串t转为十进制数a只需要一句话就可以完成：
for i:=1 to length(t) do a:=a*6+ord(t[i])-48;
使用这种方法将十进制变回六进制是一个彻头彻尾的逆向操作：当前数不断除以6并把余数作为新的最高位。比如，95除以6等于15余5，余数5就是个位，15除以6的余数3作为“十位”，最终的商2是“百位”。这叫做短除法，是最常见的方法，网上随处可见。

    下面说一下进位制中的小数。前面的东西如果理解了，小数进制的转换将顺理成章地进行下去。六进制中的0.1相当于十进制的1/6，因为六进制中的0.1、0.2、0.3、0.4、0.5五个数把区间0到1均分为了6分。同样地，(0.05)6=(5/36)10。你会发现，一个“十分位”代表1/6，一个“百分位”代表1/6^2，之前的很多结论仍然成立。六进制小数12.345就等于1*6^1+2*6^0+3*6^(-1)+4*6^(-2)+5*6^(-3)，通过负指数把进制转换的整数部分和小数部分联系在了一起。(12.345)6转为十进制后居然变成了无限小数，其实这并不奇怪，这只是一个约数的问题：同样是三分之一，在我的六进制下正好分干净(0.2)，但在你十进制下就总也分不完，总要剩一点留给下一位(0.333333…)。这里有一些小数进制转换的实例。可以看到，一个进制下的有限小数很可能是另一个进制下的无限循环小数。另一个有趣的例子在这里。
    既然前面所说的第一套方法中六进制转十进制对于小数仍然成立，那么第一套方法的十进制转六进制也可以直接在小数上使用。如果你嫌无限小数很别扭，用分数进行操作是一种不错的选择。具体操作方法和前文叙述一模一样。针对纯小数的进制转换，我们把前文的描述换种方法再说一遍：不断寻找最小的正整数x使得1/6^x不超过当前数，当前数减去1/6^x并在小数点后第x位上加一。我就不再举例子了，下面主要讨论第二套方法在小数上的应用。
    我们曾说过，在k进制末尾加0相当于该数乘以k。可惜这对小数没有用，小数后你加它八百个“0”这个数仍然不变。其实，“末尾加0”只是这种性质反映在整数上的一种现象而已，我们还需要看到更本质的东西（还记得高二哲学么）。考虑到小数的乘k和除k，不难想到这种性质的实质是小数点的移动，整数的末尾加0其实是小数点向右移动一位的结果。显然小数也有类似的结论：将k进制小数的小数点左移一位，相当于该数除以k。比如，十进制中3.14除以10就变成了0.314。结论的证明和原来完全相同：除以k后展开式中的指数全部减一，相当于所有数右移一位。有了这个结论，我们的方法就出来了。来看六进制12.345如何转换为十进制。由于这种方法对整数和小数的处理方法有一些不同，转进制时我们通常对整数部分和小数部分分别进行操作。先把12转成十进制的8，然后单独考虑小数部分。0.345可以看作是数字“5”的小数点左移，加上4后小数点再次左移，再加上3并最后一次左移小数点；写成算式即((5/6+4)/6+3)/6。展开这个式子，实质与前面的方法仍然一样。小数部分十进制转六进制依然是彻头彻尾的逆向操作：当前数不断乘以6并取出整数部分写下来。
    这里有一个实例供大家参考，这个例子中的进制转换保证不涉及无限循环小数。1/4在十进制和六进制下的表示肯定都是有限小数，因为4的唯一一个因子2同样也是10和6的因子。先看0.25怎么变成六进制：0.25*6=1.5，取出1，留下0.5；0.5*6=3，没有小数部分了，因此(0.25)10就等于(0.13)6。现在我再把它变回去：(3/6+1)/6=(0.5+1)/6=1.5/6=0.25。这不是彻头彻尾的逆操作吗？

每年NOIp前总有人问负进位制。事实上，如果你搞清了上面的问题，负进位制将非常好理解。负进位制有一个非常奇特的功能：它可以表示出负数但不需要用负号。一个负进制数可能是负数，也可能是正数。比如，负六进制下的12等于十进制下的-4，而负六进制下的123等于1*(-6)^2+2*(-6)^1+3，即十进制下的27。是正是负取决于位数的奇偶：若该数有偶数位，则该数为负数；若有奇数位，则该数为正数。原因很简单，小数点每右移一位，相当于这个数乘以-6；从一位数开始，乘奇数次后该数的位数变成偶数且值为负，乘偶数次该数仍有奇数位且值仍为正。由于末尾添0的性质（小数点移位的性质）仍然成立，负六进制与十进制的转换依然是上面的方法：(123)-6=(1*(-6)+2)*(-6)+3=(27)10。十进制转负六进制？还是那句话：彻头彻尾的逆操作。找到最小的非负整数x使得当前数减x能被6整除，这个x将作为新的最高位写到结果中，然后当前数减去x再除以-6。在这里我不说“余数”这个词，因为当除数为负数时对余数的定义很模糊。不再举例子了，例子都举烦了，自己把(123)-6=…=(27)10那一行倒过去看就是例子了。
当然，还有更神奇的：-1+i进制可以表示出复数来，因为-1+i的幂有时含有虚数有时不含虚数。运算和转换依然和上面这些东西一样，我也就不多说了。

进位制的问题结束了。我们这里是以六进制为例进行的说明，但是不要忘

Matrix67生日邀请赛完全题解发布

2007 年 5 月 15 日 / 4 条评论

题目在这里：http://www.matrix67.com/blog/article.asp?id=241

如果机房马上要关门了，或者你急着要和MM约会，请看简要题解：

1. 用类似于传统hanoi的递归方法可以做到3^n-1次。这显然是最多的了，因为总的状态数也只有3^n个。
2. 可以证明，竞赛图中不存在环当且仅当所有顶点的出度从小到大排列依次为0, 1, 2, … , n-1 。
3. 在最短路树上做树状DP，需要多叉转二叉。注意几种需要输出0的情况。
4. 搜索，算是练基本功了。用位运算优化，不加任何剪枝就能过。

否则，请慢慢阅读——

Problem 1: 为什么最少
    如果你还不熟悉Hanoi塔的解法，去题目中提到的那篇日志看看吧。如果你已经熟悉Hanoi塔的解法，你会立刻想到这道题的解法：依然是递归地解决。至于怎么递归，样例已经告诉我们了：把前n-1个金片从1号柱搬到3号柱，把第n片移到2号柱，又把那n-1片从3号柱搬回1号柱，再把第n片搬到3号柱，最后把那n-1个金片又搬过来，完成整个操作。
    我们下面解决三个问题：为什么这样不会重复出现状态，这样的移动步数是多少，为什么这样的操作步数是最多的。
    为什么这样不会出现重复的状态呢？因为我们假设前n-1个金片的移动过程中没有重复状态，而三次对n-1的调用时整个状态由于第n个金片的位置不同而不同。
    这样的方法获得的操作步数是多少呢？答案是3^n-1。我们可以用数学归纳法证明，n=1时步数为2显然正确，而f(n+1)=3f(n)+2=3*(3^n-1)+2=3^(n+1)-1。
    为什么这样的操作步数是最多的呢？废话，这样的操作步数当然是最多的，因为总的状态数也只有3^n个（每个金片的三种可能的位置确定了一种状态），你的移动步骤能比这个数目还多就见鬼了。

这道题有人用了math库，没有提供math库导致无法编译是我的失误，向大家道歉。

Hanoi问题的变种太多了，比如多根柱子、单向移动、双色金片等等。dd上次不是也出了一题么。

这题代码很短，我公布在下面。
program whyleast;


procedure solve(t,a,b:integer);
begin
   if t=0 then exit else
   begin
      solve(t-1,a,b);
      writeln(a,' ',2);
      solve(t-1,b,a);
      writeln(2,' ',b);
      solve(t-1,a,b);
   end;
end;

{====main====} var n,i:integer; ans:longint=1; begin assign(input,'whyleast.in'); reset(input); assign(output,'whyleast.out'); rewrite(output); readln(n); for i:=1 to n do ans:=ans*3; writeln(ans-1); solve(n,1,3); close(input); close(output); end.

Problem 2: 身高控制计划
    一个竞赛图是指任两个点之间都有一条有向边的图。竞赛图有很多奇妙的性质，比如一个竞赛图必然存在一条经过所有节点的路等等。
    下面我们证明，竞赛图中不存在环当且仅当所有顶点的出度从小到大排列依次为0, 1, 2, … , n-1 ：
    如果一个有向图的所有点出度都至少为1，那么这个图一定有环，因为在找到环之前DFS总可以找到新的节点。如果有向图无环，必然存在一个点没有出度。由于任两点之间都有有向边，那么其它所有点都要连一条边指向它，这样其它所有点的出度都至少为1了。删掉这个出度为0的点后剩下的图仍然无环，不断对剩下的图继续上面的过程就得到了我们的结论。
    现在我们的算法就很明确了，首先统计初始状态下的出度，然后设计某种数据结构完成两种操作：改变一个数（加一减一），询问所有数是否恰好为0, 1, 2, … , n-1 。
    统计初始状态下的出度方法有很多，这里介绍两个。首先对身高排序，然后对于每个人进行二分，寻找有序数列中该数的4/5和5/4各在什么地方。还有一种方法也是先排序，然后从左到右扫描整个序列，并保持两个指针始终指向4/5和5/4处。每次开始处理一个新的数时都把两个指针适当地右移直到超出了这个数的4/5或5/4为止。两种方法都是O(nlogn)。别以为第二种方法是线性的哦，线性算法之前还有一个排序呢。
    操作的处理也有不少方法。最简单的方法就是统计当前图中出度的数目有多少种。就是说，用a[i]表示出度为i的点有多少个，然后不断更新a[i]>0的有多少个。当这个数目等于n时我们就认为图中没有环（因为出度可能的取值只有从0到n-1共n种）。
    注意，由于同一条边可能被操作多次，因此需要一个Hash表（开散列）来判重。具体地说，你需要判断这条边以前被操作过奇数次还是偶数次，以决定哪边的出度要增加，哪边的出度要减小。

Problem 3: 狼的复仇

    把这个问题中所有的最短路都画出来是什么样子？它一定是一棵树！为什么？首先，图肯定是连通的，因为源点到任一个点都有一条最短路；其次，图肯定无环，因为源点到任一个点只有一条最短路（环的出现将意味着某些点有更短的路存在）。仔细想一下Dijkstra的算法过程，不难想到Dijkstra算法的实质就是在建这棵树——每一次由x节点加上边x-y扩展到y节点就记作x是y的父亲。注意观察上图中左图是如何变成右图的。这样，题目变成了这种形式：在有根树上，除根节点之外的其它节点中选择一些节点，使得这些节点和它们所有祖先的权值和最大。这是一个经典的树型动态规划模型。我们用f[i,j]表示以节点i为根节点的子树花费j个单位的材料最多可以得到多大的攻击力。令节点1的材料和攻击力都为0，那么最后输出f[1,0..k]中的最大值即可。决策分为两类，要么该位置建一个塔，要么把所有材料适当地分给儿子（自己就不需要再建了）。但这样的复杂度太高，我们需要用DP嵌套或者更巧妙的多叉转二叉来解决。
    DP嵌套理解起来更简单，它主要是解决这样一个子问题：若某个节点有m个儿子，我们需要寻找当j1+j2+…+jm等于某个定值时f[儿子1,j1]+f[儿子2,j2]+…+f[儿子m,jm]的最大值。这个子问题与我的某次模拟赛中论文课题选择那道DP题几乎是一模一样，看一看那道题就明白了。下面简单描述多叉转二叉的方法。

    如果你还不知道多叉转二叉的话，这道题是一个绝好的学习材料。一棵多叉树可以用“左儿子右兄弟”的方法转为二叉树，具体的说就是把多叉树转化为这种形式：节点的左儿子才是真正的儿子，节点的右儿子只是和它同辈的兄弟。注意看上图的左图是如何变成右图的。现在，我们的f[i,j]表示

OI之外的一些东西：简单谈谈排序网络

2007 年 4 月 23 日 / 134 条评论

    我们之前所有的排序算法都是给定了数据再进行排序，排序的效率很大程度上取决于数据的好坏。我们今天所介绍的是一个完全不同的排序方法，它可以在“暗箱”里对数据进行排序（即你不必知道实际数据是什么），换句话说这种排序方法不依赖于数据(Data-Independent)，所有比较操作都与数据无关。你甚至可以立即忘掉前面的比较结果，因为对于所有可能的数据这类排序算法都能得到正确答案并且排序步骤完全相同。本文结束后再回过头来看这段话你将有更深的认识。

    我们设置一个暗箱，暗箱左边有n个输入口，暗箱右边有n个输出口。我们需要设计一个暗箱使得，任意n个数从左边输进去，右边出来的都是有序的。图1显示了有4个输入的暗箱。

    暗箱里唯一允许的元件叫做“比较器”(Comparator)，每个比较器连接两个元素，当上面那个比下面那个大时它将交换两个元素的位置。也就是说，每经过一个比较器后，它的两端中较小的一个总是从上面出来，较大的总是到了下面。图2显示了一种包含4个比较器的暗箱系统。当输入数据3,1,4,2通过这个系统时，输出为1,3,2,4，如图3所示。这种暗箱结构叫做比较网络(Comparator Network)。如果对于任意一个输入数据，比较网络的输出都是有序的，那么这个比较网络就叫做排序网络(Sorting Network)。显然，我们例子中的比较网络不是一个排序网络，因为它不能通过3,1,4,2的检验。

    现在，我们的第一个问题是，是否存在比较网络。就是说，有没有可能使得任意数据通过同一组比较器都能输出有序的结果。我们最初的想法当然是，把我们已知的什么排序算法改成这种形式。把原来那十种排序又翻出来看一遍，找一找哪些排序的比较操作是无条件的。运气不错，我们所学的第一个算法——冒泡排序，它的比较就是无条件的，不管数据怎样冒泡排序都是不断比较相邻元素并把较小的放到前面。冒泡排序是一个彻头彻尾的排序网络模型，我们可以立即画出冒泡排序所对应的排序网络（图4）。这是我们得到的第一个排序网络。我们通常不认为插入排序是排序网络，因为插入排序的比较次数取决于数据的有序程度。

    传统的计算机一次只能处理一个比较。排序网络真正的研究价值在于，假如有机器可以同时处理多个比较器，排序的速度将大幅度提高。我们把比较器的位置稍微移动一下，把那些互不冲突（处理的元素不同）的比较器压缩到一层(Stage)（图5），这样整个排序过程压缩为了2n-3层。实现排序网络的机器可以在单位时间里并行处理同一层中所有的比较。此时，比较次数的多少对排序效率不起决定作用了，即使比较次数多一些但是排序网络的层次更少，效率也会更高一些。我们自然又想，排序网络需要的层数能否少于2n-3。我们想到，图5的左下角和右下角似乎有些空，我们期望能在这些位置加一些比较从而减少层数。图6给出了一个只有n层的排序网络，这叫做奇偶移项排序(Odd-even Transposition Sort)。我们下文将证明它确实是一个排序网络。这次的图很多，排版也很困难，累死我了。我把下面的图7也放到这里来了，不然到处都是图很难看。

    给出一个比较网络，怎样判断它是不是一个排序网络？很遗憾，现在还没有找到一种好的算法。事实上，这个问题是一个NPC问题。注：这种说法是不准确的，因为目前还没有迹象表明这个问题是NP问题。准确的说法应该是，“判断某比较网络为排序网络”是Co-NP Complete，而“判断某比较网络不是排序网络”（即找到一个反例）才是NP Complete。
    传统的做法是枚举所有n的排列来验证，一共要考虑n!种情况。下面我们介绍排序网络理论里最重要的结论：0-1原理(0-1 Principle)。使用这个原理来验证排序网络只需要考虑2^n种情况。0-1原理告诉我们，如果所有的01序列能够通过比较网络排出顺序，那么这足以说明该网络为排序网络。证明过程很简单。为了证明这个结论，我们证明它的逆否命题（逆否命题与原命题同真假）：如果一个比较网络不是排序网络，那么至少存在一个01序列不能被排序。我们给出一种算法，这个算法可以把任何一个不能被排序的输入数据转化为一个不能被排序的01序列。
    在最初的例子（图3）中，输入数据3,1,4,2的输出为1,3,2,4，没有成功地排出顺序，从而判断出该网络不是排序网络。这说明，输出结果中存在逆序对（左边某个数大于右边的某个数）。我们从输出结果中找出一个逆序对来。例子中，(3,2)就是我们要找的数。现在，我们把输入中所有小于数字3（左边那个数）的数都变成0，把所有大于等于3的数都变成1。这样，3,1,4,2就变成了1,0,1,0。显然，把得到的这个01序列输入进去，原来曾经发生过交换的地方现在仍然会交换，原来不曾交换的地方现在也同样不会发生交换（当两个0或两个1进行比较时，我们既可以认为它们不交换，也可以看成它们要互相交换，反正都一样）。最后，该01序列输出的结果中，本来3的位置现在还是1，原来2的位置现在仍然是0，逆序对仍然存在。因此，只要一个比较网络不是排序网络，那么总可以找到一个01序列不能被排序。等价地，如果所有的01序列都能被排序了，这个比较网络也就是排序网络了。

    我们用0-1原理来证明奇偶移项排序的正确性。我们对n进行数学归纳证明。n=2时（一个“工”字）显然是排序网络。
    图中是n=8的情况。我们假设对于所有n<=7，奇偶移项排序网络都是正确的。我们同时假定所有输入数字非0即1，下面我们说明n=8时所有的01序列都能被正确排序。
    假设最后一个数是1（图7，在前面的），那么这个1将始终排在最后不参与任何交换操作，对前面7个数没有任何影响。除去无用的灰色部分，剩下的就是n=7这一规模较小的子排序网络，由归纳假设则n=8也是排序网络；

    假设最后一个数是0（图8），那么在每一次比较中这个0都会被提到前面去（前面说过，两个0之间交不交换是一回事）。蓝色的箭头表示每个数跑到了什么位置。你会发现除最后一个数以外前7个数之间的比较器又构成了n=7的情况。

    接下来，我们提出一些比较器个数为O(n*logn*logn)的排序网络。其中一种就是之前提到过的2^p*3^q增量Shell排序。这种增量排序的特点是每一趟排序中的每个数只与前面的数比较一次，因此它可以非常方便地转化为排序网络。图9就是一个n=8的Shell排序网络。Bitonic排序也可以做到
O(n*logn*logn)的比较器个数，今天不介绍它。下面详细介绍奇偶归并排序网络。

    奇偶归并排序网络也是一种比较器个数为O(n*logn*logn)的排序网络。它和归并排序几乎相同，不同的只是合并的过程。普通归并排序的O(n)合并过程显然是依赖于数据的，奇偶归并排序可以把这个合并过程改成非数据依赖型，但复杂度将变高。这个合并过程本身也是递归的。我们假设n是2的幂（不是的话可以在前面添0补足，这对复杂度的计算没有影响），算法首先把n个数中所有的奇数项和偶数项分别递归地合并，然后在排序后的第i个偶数项和第i+1个奇数项之间设立比较器。
    假如1,4,6,8和2,3,7,9是两段已经有序的子序列，合并过程首先递归地合并1,6,2,7和4,8,3,9，这样原数列就变成了1,3,2,4,6,8,7,9。然后分别把(3,2),(4,6),(8,7)三对相邻元素中各自较小的那个交换到前面，完成合并操作。使用0-1原理证明这个结论出乎意料的简单：图10显示了n=16的情况，白色的方格代表一个0，灰色方格代表1。奇偶项分别排序后，偶数项1的个数最多比奇数项多出2个，我们设立的比较器可以考虑到所有的情况，不管什么情况都能让它最终变得有序。

    由前面说过的结论，合并过程总共需要比较O(nlogn)次。归并排序递归一共有O(logn)层，每一层总的比较器个数不超过O(nlogn)，因此总共O(n*logn*logn)。一个n=8的完整的奇偶归并排序网络如图11所示。

菜鸟献丑，漏洞百出。如果我有什么错误，各位大牛请指正。
Matrix67原创，转载请注明出处。

  外部排序(External Sort)已经在这里提到过，不再说了。
  所有排序的知识到这里说完了，下次再发布的就是数论相关内容了。数论部分将从进位制开始谈起。
  我会一直写下去，本人活到什么时候写到什么时候写完为止。不过，这几天缓一下，我计划做一个PJBlog的单版面论坛模块。

从零开始学算法：十种排序算法介绍（下）

2007 年 4 月 13 日 / 18 条评论

    那么，有什么方法可以不用比较就能排出顺序呢？借助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数组的操作可以用一次线性的扫描累加完成。
   &
nbsp;我们还需要准备一个输出数组。然后，我们从后往前扫描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原创
转贴请注明出处

从零开始学算法：十种排序算法介绍（中）

2007 年 4 月 6 日2015-01-09 / 33 条评论

本文被华丽的分割线分为了四段。对于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!)的复杂度下界。

今天写到这里了，大家帮忙校对哦
Matrix67原创
转贴请注明出处]]