曾经看到过自动扫雷软件，当时我就在想，扫雷游戏是否有什么牛B的多项式算法。最近才看到，扫雷问题居然是一个NP完全问题，并且这个定理有一个简单、直观而又神奇的证明。在这里和大家分享一下整个证明过程。
    首先，扫雷一定是NP问题，它显然可以在多项式的时间里验证一个解。接下来，我们需要把一个已知的NP完全问题归约到扫雷问题上去。我们将给出一种把逻辑电路问题归约到扫雷问题的方法，这样的话我们就可以利用扫雷问题解决逻辑电路问题，从而说明逻辑电路问题不比扫雷难。我们将把逻辑电路问题转换成一种对应的扫雷布局，就像画画一样把逻辑电路画在扫雷的棋盘上。如果你还不知道什么叫NP完全问题，什么叫逻辑电路问题，你可以看一看我的这篇文章。

   
    上图就是一条带有Boolean值的线路。注意到x和x'中有且仅有一个有雷。如果（沿线路方向）前一个格子有雷，我们就说这条线路状态为True；反之如果后一个格子有雷，那么这条线路所传递的Boolean值就是False。每条线路的起始端都如下图左所示，其中符号*表示该格里必然有雷，x和x'中同样是有且仅有一个有雷，但到底是哪一个里面有雷谁也说不清楚。线路是可以拐弯的，如下图右所示，这可以保证转角后Boolean值相同。
   

查看更多 »

    在这篇文章里，我们从信息论的角度证明了，基于比较的排序算法需要的比较次数（在最坏情况下）至少为log2(n!)，而log(n!)=Θ(nlogn)，这给出了比较排序的一个下界。但那里我们讨论的只是最理想的情况。一个事件本身所含的信息量是有大小之分的。看到这篇文章之后，我的思路突然开阔了不少：信息论是非常强大的，它并不只是一个用来分析理论最优决策的工具。从信息论的角度来分析算法效率是一件很有趣的事，它给我们分析排序算法带来了一种新的思路。

    假如你手里有一枚硬币。你希望通过抛掷硬币的方法来决定今天晚上干什么，正面上网反面看电影。投掷硬币所产生的结果将给你带来一些“信息”，这些信息的多少就叫做“信息量”。如果这个硬币是“公正”的，正面和反面出现的概率一样，那么投掷硬币后不管结果咋样，你都获得了1 bit的信息量。如果你事先就已经知道这个硬币并不是均匀的，比如出现正面的概率本来就要大得多，这时我们就说事件结果的不确定性比刚才更小。如果投掷出来你发现硬币果然是正面朝上，这时你得到的信息量就相对更小（小于1 bit）；反之如果投掷出来居然反面朝上了，那你就得到了一个相对较大的信息量（大于1 bit）。但平均下来，我们得到的信息量是小于1 bit的，因为前者发生的可能性毕竟要大一些。最极端的情况就是，这是一枚被捣了鬼的魔术硬币，你怎么投都是正面。此时，你投了硬币等于没投，反正结果都是正面朝上，你得到的信息量永远为0。
    这个理论是很符合生活实际的。昨天晚上我出去吃饭时，坐在我后面的那个人是男的还是女的？这种问题就比较有价值，因为大家都猜不到答案究竟是什么；但要问我昨天跟谁一起出去上自习去了，问题的答案所含的信息量就变小了，因为大家都知道如果我破天荒地跑去自习了的话多半是有MM陪着一起去的。如果有网友问我是男的还是女的，那就更不可思议了，因为我不但多次在这个Blog里提到我一直想找一个合适的MM，还在AboutMe里面发了我的照片。如果某人刚操完一个MM，突然扭过头去问“对了，你是男的还是女的呀”，那这个人绝对是一个不折不扣的大傻B，因为这个问题所能带来的信息量几乎为0。
    总之，当每种结果出现的概率都相等，事件的不确定性达到最大，其结果最难预测时，事件的发生将会给我们带来最大的信息量。我们把一个事件的不确定程度叫做“熵”，熵越大表明这个事件的结果越难以预测，同时事件的发生将给我们带来越多的信息。如果在排序算法里每次比较的熵都是最大的，理论上来说这种（基于比较的）排序算法就应当是最优的。但我们一会儿将看到，我们已知的排序算法总是不完美的，每种算法都会或多或少地存在一些价值明显不大的比较。

查看更多 »

图片来源：http://xkcd.com/399/
号外：期待了9个多月的PSP游戏Echochrome已经发行，网上到处有下载

  
    有这样的一类组合游戏，对于任一个游戏局面，游戏双方的合法决策都完全一样，游戏对战双方的唯一区别就是看谁先走。这样的游戏叫做Impartial Games。像什么报数啊，取火柴啊，取石子啊，这些游戏都属于Impartial Games；而象棋、围棋等要分棋子颜色的游戏则不属于Impartial Games。共享状态的游戏几乎没有可玩性，因为游戏开始前我们就能知道谁赢谁输（如果双方均使用最佳策略）。棋局的任一状态只有两种，面对这个棋局的人要么必胜要么必败。考虑这样的一个递推关系：如果一个状态是必胜态，那至少有一种走法能走成一个必败态留给对方；如果一个状态是必败态，那它怎么走都只能走到必胜态。运用这样的关系，我们可以自底向上推出初始状态是必胜还是必败。
    近来有人提出一个名为Atropos的游戏，它就是一个即使计算机也很难办的Impartial Game，它能保证这个游戏仍然具有可玩性。游戏在一个Sperner三角形上进行，上图就是一个边长为7的Sperner三角形。游戏开始后，双方依次在白色的圆圈里涂上红色、绿色或者蓝色，已经涂过颜色的圆圈不能再涂色。另外，只要有可能，所涂的圆圈都必须紧挨着上次对方涂的那个圆圈。谁先涂出三种颜色都有的小三角形，谁就输掉这场游戏。

  
    注意这个游戏是不可能出现平局的。当所有白色圆圈全部涂上了颜色后，至少会出现一个红绿蓝小三角形。为了证明这一点，我们可以在所有的绿色和红色圆圈中间画一个箭头，红的在箭头右边，绿的在箭头左边。这些箭头一定组成了一条一条的路径，它们既不会交汇也不会分岔。但整个图的边界上进来的箭头有4个，出去的箭头只有3个，于是至少有一条路径在里面走死了，也即迎面碰上了蓝色的圆圈。这样，我们就找到了一个红绿蓝三色都有的小三角形。

    这个游戏虽然属于Impartial Games，但它仍然具有可玩性。从直觉上看，这个游戏中的先手后手几乎没有区别，谁也不占优势。这篇论文则严格证明了，判断Atropos游戏的最佳策略属于PSPACE-complete，这是所有使用多项式空间的问题中最难的一类，所有使用多项式空间的问题都可以（在多项式的时间内）约化到它。这说明，Atropos游戏没有什么很显然的“决窍”，即使利用计算机也很难确定最优决策。

在线游戏：http://cs-people.bu.edu/paithan/spernerGame/SpernerGame.html (Java Applet)
查看更多：http://cs-people.bu.edu/paithan/spernerGame/

    SETI@home可以在杂乱的射电数据中搜寻独特的讯号，你能在大街上的嘈杂声中清晰分辨出一个尖细的女声大叫“亚美蝶”。这些现象都表明，有时对集合里的所有元素进行整体考察可以很快找出我们所要找的个体。去年我们搞合唱比赛时，我又想到了一个绝佳的例子：你可以在合唱声中清楚地听到是否有人跑调。考虑这样一个问题，假如合唱团里有一个人唱歌始终走调，但我听不出来是谁走调，只能听出当前正在唱歌的人中是否有唱走调了的人。那么，我如何才能迅速地揪出那个唱走调的人？利用经典二分法，我们可以在log2(n)次合唱后找出唱走调了的人。每一次，我都把剩下的人平均分成两组，然后选其中一组来合唱：如果听不到走调的声音，这一组的人就全部过关；如果听到有人走调，那另一组里的人都可以被排除了。递归地对剩下的组进行同样的操作，log2(n)次操作后必定可以找出那个唱歌走调的人。
    现在的问题变得有些麻烦了。假如我们知道合唱队里有一个人唱歌爱跑调，但他不是总会跑调。具体地说，他只有1/2的概率唱错，但其余1/2的时间里他却唱得很准。现在，传统的二分法不再适用了，因为没有走调声已经不能起到排除的作用了。你能想出多少种可行的算法来找出那个人？下面提出一些可行的方法，你认为哪种方法更好？你能求出这些算法所需要的检测次数的期望值各是多少吗？

    1. 不断地随机生成一个大小为n/2的子集并对其进行检测，直到某次不能通过检测为止，然后递归地对其进行操作。
    2. 所选的子集大小为n/2是最优的吗？把上面这种方法的n/2改成n/a，常数a的最优值是多少？
    3. 检测次数的期望值还可以更小吗？我们想到，每次都重新生成一个新的集合其实并不科学，新集合本身是否包含老鼠屎也是得碰碰运气的。因此，对方法1的一个合理改进是：把集合平均划分为两个部分，交替对它们进行检测直到某次检测没通过为止，然后对该组递归操作下去。这种方法真的比前两种好吗？它所需要的期望次数是多少？
    4. 尝试对方法3进行改进。如果把集合平均划分成3份并循环进行检测，效果会不会更好一些？





































    1. 选取的子集有1/2的概率覆盖了我们要找的那个人，子集里有他而他这次恰好又唱走调了则有1/4的概率。因此，不管规模有多大，平均需要4次才能把规模缩小一半。因此，检测次数的期望值为4*log2(n)。为了方便比较期望值的大小，后面的答案我们一律表示成一个常数乘以log2(n)的形式。
    2. 类似地，平均需要2a次检测才能把规模缩小到原来的1/a，因此总共花费的检测次数为2a*log2(n)/log2(a)。对函数求导，可得当a为e时函数值达到最小。此时的检测次数期望值为2e*log2(n)/log2(e)≈3.7683 * log2(n)。
    3. 这个就经典了。设方法3里把规模缩小一半所需要的检测的期望次数为m，下面我们来看m应该等于多少。把n个人平均分成两组，我们要找的老鼠屎有1/2的概率在第一组，有1/2的概率在第二组。因此，第一次就测出问题来有1/4的可能，第二次就测出问题也有1/4的可能。对于剩下的1/2种情况，局面变得又和最开始一样，只是平均需要的检测次数比原来多了2。根据期望值的定义，有m=(1/4)*1 + (1/4)*2 + (1/2)*(m+2)，解得m=3.5。总的检测次数就是3.5 * log2(n)，它比前面两种方法都要好。你可能不同意上面求m的方法。这没啥，如果你不断对m进行迭代，你会发现展开出来的式子就是最标准的期望值定义。
    4. 类似地，有m=(1/6)*1 + (1/6)*2 + (1/6)*3 + (1/2)*(m+3)，解得m=5。于是，把规模缩小到原来的1/3平均需要5次检测，总的检测次数为5*log2(n)/log2(3)≈3.1546 * log2(n)。

题目来源：IBM Ponder This Dec07
原文还从熵的角度探寻了问题的最优算法，感兴趣的读者可以去看一看

    似乎MM都很喜欢拼图游戏。如果MM过生日你不知道送她什么，送她一副拼图是一个不错的选择（事实上原来我也曾干过这事）。如果你失恋了，或者挂科了，或者这个月没饭钱了，或者怀疑自己的性取向，感到很郁闷的时候，静下心来玩一玩拼图游戏可以让你暂时忘掉烦恼。当你最终完成整个拼图时，你会有前所未有的成就感。当然，只有那些有耐心的人才觉得拼图有趣，像我这样的人肯定拼个十几二十分钟就觉得烦了。计算机搞久了的人往往都很没耐心，同一个操作反复执行的次数多了就觉得很烦，心里总会想这种机械操作交给傻B计算机去做该多省事啊。有时我会想，计算机是否有什么牛B算法可以用来解决拼图问题。今天我们要研究的是，如何把拼图游戏描述成一个信息学问题，计算机是否有更高效的算法来解决这个问题。
    传统的拼图一共有w*h个正方形小块，最终将拼成一个w*h的矩形图案。我们大致有以下两种依据来确定一个小块的位置：根据这一小块上的图案来确定它在整幅图片中的位置，或者从形状上观察这一小块可以和其它哪些块拼接。于是，拼图游戏变成了这样一种交互式的问题：允许你询问某一块是否在指定的位置，或者某两块是否相连，你如何尽早地完成整个拼图。具体地说，你可以：

• 询问拼块A是否在(x,y)上，交互库返回yes/no
  
• 询问拼块A和拼块B是否相连，交互库返回yes/no

    有时候，你并不能把拼图完全当作一个顶点最大度为4的无向图。多数情况下两个拼块只能按某一个方向上的某一种顺序相连。为了更贴近拼图游戏的真实情况，我们可以假定，对于第二个问题如果返回的是yes，则交互库还会告诉你A应该接在B的什么方向。现在的问题是，完成整个拼图最少需要多少次询问？
    假如拼图共有n块，询问的次数不会超过O(n^2)。对于每一个拼块，我都像傻B一样挨着挨着询问“它是不是在这里”，O(n^2)次询问可以保证我完成整副拼图。我们希望知道，是否有算法可以使用O(nlogn)甚至更少的询问次数？



































    答案是否定的。对于拼图问题，计算机并没有英明到哪里去，它也只能像傻B一样一个一个去试。我们下面将证明，不管你怎么努力，询问次数再怎么也不会低于O(n^2)。首先我们需要说明的是，问题2实际上并不能带给我们多大的帮助。

      
    如上图，我们把整个拼图划分成一个一个的“十字架”，并且挖掉每个十字架正中间的那个格子（深灰色的格子）。注意到关于这种划分的三个重要性质：

• 每个浅灰色的格子最多与一个深灰色的格子相邻
  
• 任何两个深灰色的格子都不相邻
  
• 深灰色的格子共有n/5个（可能有常数级别的偏差）

    现在，假如整个拼图里只剩这些被挖掉的深灰色格子还没确定，其它的格子上都已经放好了正确的拼块。再换句话说，在拼图游戏过程中，拼块是否应放在浅灰色的格子里，若可以则应该放在哪个格子，以及浅灰色格子之间的邻接状态都是已经知道的了，只要是不涉及深灰色格子的信息，你要什么我就给你什么。此时，我们只剩下n/5个格子（仍然是O(n)个格子），并且询问1与询问2变得完全等价；你要问拼块A和拼块B是否相邻，还不如直接问拼块是否应放在某个洞里。于是，问题变为这样，只凭借询问1来确定O(n)个拼块的位置需要多少次询问。我们下面证明，O(n^2)次询问是必须的。
    考虑一个二分图，左边n个顶点表示n个拼块，右边n个顶点表示拼图上残留的n个洞。现在，我只能询问指定的两顶点间是否有边，只有当交互库回答了n次yes后拼图才算完成。那么，作为交互库，你应该尽可能返回对游戏者不利的信息，让整个局面往最坏的方向发展。如果叫你来写这个交互库，你该怎么写？容易想到，只要有可能，我都返回no；除非某个时候一旦我再返回一次no，所有没被问过的边和返回过yes的边所组成的二分图不存在一个完全匹配时，我才可能返回yes。我们需要一个二分图存在完全匹配的充分条件来支持我们的这个算法。
    考虑如下定理：如果一个二分图左边右边各有n个顶点，每个顶点都与对面至少n/2个顶点相连，则这个二分图一定存在一个完全匹配。定理的证明很简单。König定理告诉我们，二分图的最大匹配数应该等于最小点覆盖集，而一个图的最小点覆盖与最大点独立集是互补的，它们的和始终等于顶点数|V|（在这里|V|=2n）。因此我们只需要证明，上述二分图的最大点独立集不会超过n。假如我在左边选的顶点数不超过n/2个，则右边最多也只能选n/2个顶点（左边任一个点都已经使右边至少n/2个点废了）；假如我左边选的顶点数超过了n/2个，则右边的顶点一个都不能选（右边每个点都连接了左边至少n/2个点，任选一个都会导致冲突）。总之，最大点独立集不可能超过n，但n显然是可以达到的（取同一边的所有点），那么最小点覆盖集也就是n，即二分图存在完全匹配。
    有了这个定理，下面我就好办了：任何时候，只要每个顶点你都有半数以上的边没问过，我就可以放心大胆的回答no（因为这些没问过的边总可以组成一个完全匹配）；一旦某个时刻有一个顶点被问过了n/2次，那么我就随便找一个完全匹配，把这个点“亮”出来，告诉你这个点应该和哪个点匹配（不计询问次数），然后把这两个匹配了的顶点从图中删去，继续刚才的操作。每次删除一对顶点都会顺带着删掉与它们相连的至少k/2条问过的边，其中k表示当时左边右边各剩下k个顶点。删掉了多少边就表示你曾问过了多少边，因此完成整个拼图你总共问过至少n/2 + (n-1)/2 + ... + 2/2 + 1/2条边，这个数量显然是O(n^2)的。

做人要厚道
转贴请注明出处
参考资料：http://www.brand.site.co.il/riddles/200710q.html

    我们之前所有的排序算法都是给定了数据再进行排序，排序的效率很大程度上取决于数据的好坏。我们今天所介绍的是一个完全不同的排序方法，它可以在“暗箱”里对数据进行排序（即你不必知道实际数据是什么），换句话说这种排序方法不依赖于数据(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的单版面论坛模块。

    那么，有什么方法可以不用比较就能排出顺序呢？借助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原创
转贴请注明出处