Matrix67 |
2009-05-30 1:49 | 
网上有各种直观的排序算法图形化演示（见这里和这里），我自己也曾经做过一个。
今天我看到了一个我所见过的最酷的、最可爱的排序算法演示。
某网站被干掉了后，大家会错过很多精彩的视频。我注册了一个土豆网的帐号，把一些精彩的视频搬过来与大家分享。
May
30
Apr
20
昨天我突发奇想，写了几段Mathematica代码，生成了各种排序算法的内存变化图。图中每一个新的横行都表示数组的一次更新，数字大小用颜色来表示。你可以直观地看到这些算法是如何把乱序数组一点一点变为有序的。效果还是很令人满意的，不少算法的内存轨迹都相当美观，相当有艺术性。
图很大，我就不在首页上显示了，大家点“查看更多”看图吧。
Mar
6
上次我们谈到，我们考虑时间复杂度时往往假设任意大的整数运算（赋值、四则运算、取余运算、比较运算、位运算包括左移右移）都可以在常数时间内完成，殊不知这留下了一个非常具有研究价值的漏洞：能否利用计算机理想模型中的整数运算，把问题打包成超大整数后并行计算，从而办到一些在普通计算机上无法办到的事情？我们在上一次的文章中介绍了利用“大整数随便算”的漏洞“耍赖”得到了一个线性时间的排序算法。这个漏洞真的已经被充分利用了吗？我们还能从里面榨出多少汁水来？令人无法想象的是，线性时间的排序算法远远没有挖掘到理想大整数运算的巨大潜力，事实上我们能做到常数时间的排序！问题和解答仍然来自Using your Head is Permitted，在这里向Michael Brand表示深深的膜拜。
自然，说“常数时间排序”是有前提条件的，否则即使读入输出也得耗费线性的时间。不过，我们可以假设所有待排序的数都已经打包进一个大整数里，输出时也无需解包，直接返回另一个大整数即可。在这样的情况下，我们完全可以用常数时间完成排序。换句话说，我可以用O(1)的时间，“一下子”就把0100 0111 0001 0010变成0001 0010 0100 0111，不管这个大整数里面装了多少个数。为了方便大家阅读和思考，我们再取一些名字，方便描述。我们把由多个数构成的大整数叫做“整数串”。整数串中所含的数都是二进制，它们用空格隔开。整数串中每个数的位数都必须相等，位数不够用零补足。我们把这个位数叫做“定宽”，本文例子的定宽都是4。
Jan
10
当我们研究复杂度时，我们往往会将现实机器进行理想化。例如，我们说冒泡排序是O(n^2)的，这其实是不准确的。这个论断假设整数之间的比较运算是O(1)的，而事实上它们是O(log(min(|a|,|b|)))的。多数时候我们都认为这种机器模型的理想化是合理的，毕竟这让问题简化了不少，并且也能反映出算法的本质。但大家有想过吗，这个“大整数随便算”的假设其实是一个超级大漏洞，我们可以利用理想模型中的这一漏洞来作弊，获得时间复杂度更低的算法。上个月，Michael Brand在他的UyHiP里就提出了这样一个问题：假设计算机对任意大整数的赋值、四则运算、取余运算、比较运算、位运算（包括左移右移）的复杂度都是常数级别，你能否设计出一个O(n)的排序算法来？
我非常喜欢这个题目。月初的时候我就提交了一个正确的算法。我们将用左移和加法运算把整数序列编码成一个超大整数，然后利用排序网络进行并行排序。这个算法比较复杂，你可以按照下面的思路一步一步得到这个算法。
1. 如何用位运算来取绝对值？
2. 给出两个正整数a, b，不用比较运算和判断语句如何把小数赋给a，大数赋给b？
提示：和加差除以2等于大数，和减差除以2等于小数3. 如何利用位运算把整数序列编码成一个超大整数？
例如把（二进制数）11, 1011, 1110, 1编码为一个数00011 01011 01110 000014. 如何用位运算给超大整数中的所有数同时取绝对值？
5. 给出两个超大整数a, b，不用比较运算和判断语句如何把对应位置上的小数赋给a的对应位置，大数赋给b的对应位置？ 例如把
a = 000010 000111 000100 001001
b = 000001 001011 000011 011111
变成
a = 000001 000111 000011 001001
b = 000010 001011 000100 0111116. 如何实现奇偶移项排序？
最后，由于奇偶移项排序只有O(n)层，因此整个算法是O(n)的。
但是，这个算法太繁琐了，不具有美观性。虽然这个算法是我自己想出来的，但我仍然很不满意。待我看了这个月Michael Brand发布的答案后，我一拍大腿，哎呀，还有一个如此简单巧妙的算法我没想到！相比之下，我的算法太复杂了，原因就在于我还没有充分挖掘到“大整数的常数级运算”的潜力。这个理想模型的假设太强大了。打开思路，放宽思维，大胆想象，从更大的尺度上来思考，我们可以得到一个简单得出奇的线性排序算法来。
Oct
25
今天是10月25日。祝古汉MM生日快乐。
曾经有一段时间这个Blog的访问量和订阅量剧增，后来才知道因为这个Blog上的一道牛B题目被出成POJ的月赛题了。那道题目真的很好玩，题目和解答都很简单有趣。其实我挺喜欢这种“给出一个算法并证明该算法最优”类型的数学题目。这里再和大家分享一个类似的比较老的题目，有兴趣的话不妨先想想再看答案。
一次“交换”操作是指将数列中的两个数位置对换。我们假设，互不相交的若干个交换操作可以一次同时进行；换句话说，如果k个交换中任两个都不会对同一个数进行操作，那么这k个操作可以并行完成。例如，在数列
10, 6, 8, 5, 2, 3, 1, 4, 7, 9
中，我们可以同时交换第4个数和第6个数，第8个数和第9个数，以及第3个数和第7个数。经过这一次“并行交换”后，数列变为：
10, 6, 1, 3, 2, 5, 8, 7, 4, 9
任意给定一个长度为n的全排列，请问对该序列进行排序最坏情况下需要多少次并行交换？给出一种具体的算法，说明这个次数足够了；并且给出一种最坏情况，证明这个次数是必需的。
Oct
4
上次那篇日志发布之后，据说大家解题的热情相当高。Michael Brand告诉我说，他收到了很多来自中国的邮件，他感到非常高兴。在揭晓谜底之前，还是让我们先回顾一下题目：
对数列的一次“块移动”是指把一段数取出来插入到数列中的另一个地方（说穿了就是一次选择剪切粘贴的操作）。例如，数列1,4,5,6,2,3,7可以通过一次块移动完成排序（把456挪到3后面）。那么，想要让一个1到n的逆序排列n, n-1, ..., 3, 2, 1变为顺序排列，最少需要多少次块移动？给出你的算法，并证明这个移动数目不能再少了。
需要指出的是，答案并不是n-1那么简单。当n=5时，只需要三步就可以搞定了：
5 4 [3 2] 1
3 2 5 [4 1]
[3 4] 1 2 5
1 2 3 4 5
Sep
3
Michael Brand的Using your Head is Permitted是我最喜欢的谜题挑战网站，很多题目相当精彩。我已经多次翻译了那上面的谜题（点击这里看看）。不过，以往我都是静候月底释出答案，从来没有想过参与挑战。这个月的题相当诱人，只看题目描述的最后一句话我就知道这绝对是我喜欢的类型，于是我有了向本月题目发起挑战的冲动。印象中我真的是很久很久没有像这样疯狂地思考一个问题了。然后呢，我非常得意地告诉大家，哈哈~~~经过昨天一整夜的思考，我终于把它解决了！！于是赶忙写下我的解答过程，再三检查后发到了Michael Brand的邮箱。今天起床时收到了Michael Brand热情洋溢的回信，List of solvers也写上了我的名字，我很是兴奋。自我感觉这是一道非常好的题目，题目简洁有趣而有挑战性，解答本身并不难但也不太好想，很适合大家花一整天的时间仔细琢磨；因此这里也推荐给大家来挑战一下。解答不要发到下面的评论里，也不用发给我，直接发过去好了。期待过几天在List of solvers里看到大家的名字。
在这里简单翻译一下题目。对数列的一次“块移动”是指把一段数取出来插入到数列中的另一个地方（说穿了就是一次选择剪切粘贴的操作）。例如，数列1,4,5,6,2,3,7可以通过一次块移动完成排序（把456挪到3后面）。那么，想要让一个1到n的逆序排列n, n-1, ..., 3, 2, 1变为顺序排列，最少需要多少次块移动？给出你的算法，并证明这个移动数目不能再少了。
Update: 为防止进一步讨论，我把评论禁了…
May
30
在这篇文章里，我们从信息论的角度证明了，基于比较的排序算法需要的比较次数（在最坏情况下）至少为log2(n!)，而log(n!)=Θ(nlogn)，这给出了比较排序的一个下界。但那里我们讨论的只是最理想的情况。一个事件本身所含的信息量是有大小之分的。看到这篇文章之后，我的思路突然开阔了不少：信息论是非常强大的，它并不只是一个用来分析理论最优决策的工具。从信息论的角度来分析算法效率是一件很有趣的事，它给我们分析排序算法带来了一种新的思路。
假如你手里有一枚硬币。你希望通过抛掷硬币的方法来决定今天晚上干什么，正面上网反面看电影。投掷硬币所产生的结果将给你带来一些“信息”，这些信息的多少就叫做“信息量”。如果这个硬币是“公正”的，正面和反面出现的概率一样，那么投掷硬币后不管结果咋样，你都获得了1 bit的信息量。如果你事先就已经知道这个硬币并不是均匀的，比如出现正面的概率本来就要大得多，这时我们就说事件结果的不确定性比刚才更小。如果投掷出来你发现硬币果然是正面朝上，这时你得到的信息量就相对更小（小于1 bit）；反之如果投掷出来居然反面朝上了，那你就得到了一个相对较大的信息量（大于1 bit）。但平均下来，我们得到的信息量是小于1 bit的，因为前者发生的可能性毕竟要大一些。最极端的情况就是，这是一枚被捣了鬼的魔术硬币，你怎么投都是正面。此时，你投了硬币等于没投，反正结果都是正面朝上，你得到的信息量永远为0。
这个理论是很符合生活实际的。昨天晚上我出去吃饭时，坐在我后面的那个人是男的还是女的？这种问题就比较有价值，因为大家都猜不到答案究竟是什么；但要问我昨天跟谁一起出去上自习去了，问题的答案所含的信息量就变小了，因为大家都知道如果我破天荒地跑去自习了的话多半是有MM陪着一起去的。如果有网友问我是男的还是女的，那就更不可思议了，因为我不但多次在这个Blog里提到我一直想找一个合适的MM，还在AboutMe里面发了我的照片。如果某人刚操完一个MM，突然扭过头去问“对了，你是男的还是女的呀”，那这个人绝对是一个不折不扣的大傻B，因为这个问题所能带来的信息量几乎为0。
总之，当每种结果出现的概率都相等，事件的不确定性达到最大，其结果最难预测时，事件的发生将会给我们带来最大的信息量。我们把一个事件的不确定程度叫做“熵”，熵越大表明这个事件的结果越难以预测，同时事件的发生将给我们带来越多的信息。如果在排序算法里每次比较的熵都是最大的，理论上来说这种（基于比较的）排序算法就应当是最优的。但我们一会儿将看到，我们已知的排序算法总是不完美的，每种算法都会或多或少地存在一些价值明显不大的比较。
