上次我们谈到，我们考虑时间复杂度时往往假设任意大的整数运算（赋值、四则运算、取余运算、比较运算、位运算包括左移右移）都可以在常数时间内完成，殊不知这留下了一个非常具有研究价值的漏洞：能否利用计算机理想模型中的整数运算，把问题打包成超大整数后并行计算，从而办到一些在普通计算机上无法办到的事情？我们在上一次的文章中介绍了利用“大整数随便算”的漏洞“耍赖”得到了一个线性时间的排序算法。这个漏洞真的已经被充分利用了吗？我们还能从里面榨出多少汁水来？令人无法想象的是，线性时间的排序算法远远没有挖掘到理想大整数运算的巨大潜力，事实上我们能做到常数时间的排序！问题和解答仍然来自Using your Head is Permitted，在这里向Michael Brand表示深深的膜拜。
自然，说“常数时间排序”是有前提条件的，否则即使读入输出也得耗费线性的时间。不过，我们可以假设所有待排序的数都已经打包进一个大整数里，输出时也无需解包，直接返回另一个大整数即可。在这样的情况下，我们完全可以用常数时间完成排序。换句话说，我可以用O(1)的时间，“一下子”就把0100 0111 0001 0010变成0001 0010 0100 0111，不管这个大整数里面装了多少个数。为了方便大家阅读和思考，我们再取一些名字，方便描述。我们把由多个数构成的大整数叫做“整数串”。整数串中所含的数都是二进制，它们用空格隔开。整数串中每个数的位数都必须相等，位数不够用零补足。我们把这个位数叫做“定宽”，本文例子的定宽都是4。
排序
趣题：理想模型下的排序算法（上）
当我们研究复杂度时，我们往往会将现实机器进行理想化。例如，我们说冒泡排序是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发布的答案后，我一拍大腿，哎呀，还有一个如此简单巧妙的算法我没想到！相比之下，我的算法太复杂了，原因就在于我还没有充分挖掘到“大整数的常数级运算”的潜力。这个理想模型的假设太强大了。打开思路，放宽思维，大胆想象，从更大的尺度上来思考，我们可以得到一个简单得出奇的线性排序算法来。
趣题：用最少的“并行交换”完成排序
今天是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的全排列，请问对该序列进行排序最坏情况下需要多少次并行交换？给出一种具体的算法，说明这个次数足够了；并且给出一种最坏情况，证明这个次数是必需的。
趣题：用最少的块移动实现逆序操作
上次那篇日志发布之后，据说大家解题的热情相当高。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
思考的乐趣：UyHiP趣题之用最少的块移动实现逆序操作
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: 为防止进一步讨论，我把评论禁了…