书架的某一层里放了一套百科全书，但它们排列的顺序却是乱的。一个傻子想要把这套书排好顺序，也就是说他想要书架里的书从左至右分别是第 1 卷，第 2 卷，……，第 n 卷。他给这套书排序的办法是这样的：不断取出一本原应放在更左边的书，插进它该在的位置。比方说，某本书的卷号是 3 ，它的位置却是左起第 5 ，位于其目标位置的右侧。那么傻子就可以把这本书拿出来，插入当前左起第 2 本书的右边，把那些占了它位置的书挤到更右边去，而不管这一操作是否会破坏掉已经就位的书。注意到这种排序法很可能捡了芝麻，丢了西瓜，为了一本书的位置而破坏掉一连串原已排好的书，可谓是鼠目寸光，缺乏远见。我们的问题是，在哪些情况下这样的排序法最终一定能实现排序，哪些情况下可能会陷入永无止境的死循环？
出人意料的是，这种看上去明显有漏洞的排序法竟然是一种正确的排序算法——对于任意一个初始序列，采用这种方法总能让序列最终变得有序。为了证明这一点，我们按照如下方式把序列编码为 n 位的 01 串：左起第 i 位为 1 当且仅当第 i 卷在正确的位置上。序列 7, 2, 1, 4, 3, 5, 6, 8, 9 就被编码为 010100011 ，因为在这 9 本书当中，只有卷 2 、卷 4 、卷 8 和卷 9 在正确的位置上。
如果某一次操作中，傻子把第 k 卷放进了正确的位置，那么考虑所有卷数小于 k 的书：如果它原本就在左起第 k 本书的左边，这个操作影响不到它；如果它原本就是左起第 k 本或者更右边的书（这表明它原本就不在正确的位置上），那么现在它仍然不可能在正确的位置上（它的位置只可能不变或者更靠右了）。因此，编码的前 k-1 位是不动的，但第 k 位从 0 变成 1 了。这就意味着，任意一个操作总会让整个二进制编码变大。而容易看出，只要序列不是有序的，傻子总有可以操作的对象，因此序列编码将不断增加，最终将变成 111…11 。此时所有书都在它应该在的位置上，整个序列也就有序了。
现在，又来了另外一个傻子。他的排序办法和前一个傻子基本上相同，唯一不同的是，他每次都可以选择任意一本不在原位的书（并把它放进它应该在的位置），而不仅仅是选择那些位于目标位置右侧的书。这个傻子的排序方法还能保证最终总会让这排书变得有序吗？
答案竟然再一次是肯定的——这种方法最终总能让所有序列变得有序。为了证明这一点，只需要注意到，只要序列不是有序的，傻子总能找到合法的操作，因此只要不存在循环，序列最终一定会变得有序。我们将用反证法证明，傻子的操作一定不会让状态产生循环。
假设存在一个循环，并且在某一步，傻子取出了第 k 卷，并且无妨假设它被移动到了更右边的某个位置。由于这是一个循环，因此在某个时候它又跑回了目标位置的左边。这说明，傻子一定取出了一本卷号比 k 更大的书，放到了 k 的右边，并把 k 挤到左边去了。只需要令 k 为循环中被挪到右边的书中卷号最大的一本，矛盾就产生了。
我们自然会提出这样一个问题：这种排序算法的效率如何？换句话说，最坏情况下傻子排序法需要操作多少步？今年一月和二月的 UyHiP 谜题中， Michael Brand 详细地讨论了这个问题，有兴趣的朋友可以看看：
http://www.brand.site.co.il/riddles/201001q.html
http://www.brand.site.co.il/riddles/201002q.html
沙发？？？
激动ing……
这种方法我们经常用，比如打扑克拿牌的时候，采用第二种方法
我写的证明Michael Brand看不懂，555555
好东西。
貌似这样还不算傻，哈哈
其实他们都不是傻子啊，好像很聪明啊
看来也不是傻子啊，哈哈
我认为两个傻子本质上还是基数排序 但是只有傻子决定调整最小或最大编号的书时才会造成一次有效的基数排序步骤，完成这次步骤后被调整的书不再改变位置，之后再对剩余的书递归地采用此规则，就证明了他们方法的正确性，这样看来第二个傻子的方法更有效率些，当然，他们决定调整一个不大不小的书时所作的工作就很可能无效了，这造成他们的方法效率很低
傻子好聪明……
不愧是学哲学的
突然想问一下您用啥软件处理这种图的？
于是不计效率的……
恩，排序学的防呆设计？
“只要存在无序，就有可操作步骤”
这个思想值得推敲
第二种方法只是证明了通过某种方式可以跳出死循环，而机器运算不会去做这样的尝试！
不错…
呵呵，有意思，我用python代码证明了都是可以的！请见：http://hi.baidu.com/pyleaf/blog/item/dbd080e958137adfd439c936.html
为什么是傻子……
很聪明的傻子呀……
呵呵，但我想这样的排序不会是最快的
貌似第一个傻子是直接插入排序算法
@horseluke
和直插在原则上不一样吧。
直插是依次处理各个元素，n次之后排好。
排好之前是不知道哪个元素应该放在哪的。
但是这个图书，傻子排好它之前，是知道某本书本应在哪的。
这才会出现“原应放在更左边的书”这样一说。
这傻子不太傻！
板凳聪明
挺聪明的
，傻子把第 k 卷放进了正确的位置，那么考虑所有卷数小于 k 的书：如果它原本就在左起第 k 本书的左边，这个操作影响不到它；如果它原本就是左起第 k 本或者更右边的书（这表明它原本就不在正确的位置上），那么现在它仍然不可能在正确的位置上（它的位置只可能不变或者更靠右了）。因此，编码的前 k-1 位是不动的，但第 k 位从 0 变成 1 了。这就意味着，任意一个操作总会让整个二进制编码变大。
若是623451，在1插入到正确的位置之后，序列变为162345， 二进制编码变小
若每次都能使得二进制编码值增加，则可保证线性时间排序，但很明显该方法不能
@拜月教徒
623451是011110,162345是100000,显然后者大
这个我觉得扩展的插入排序，复杂度和插入排序的复杂度是相同的，尤其说的第二个傻子，很明显，已经是一个插入排序，只不过可以往两端插而已，反证法中其实已经限制了傻子在插入时的规则
这个顺序挺让人纠结的！
关于第一个算法的正确性证明的补充：
证明应该改成这样：任何比k小的位置的元素（第1,2…k-1）是不会移动的。所以二进制编码中的高k-1位不变，而由于第k位从0变成了1。所以整个n位二进制数是在变大的。每一次变动二进制数都在增长，最多需要2^n-1次即可排序成功，所以最坏复杂度是指数阶的。
关于第二算法正确性证明的补充：
每一次排序，相当于，某一个n位二进制数变成了另外一个n位二进制数。如果存在一个不重复的n位二进制数序列，对应于这样一次排序。那么这个序列最大的长度就是2^n。在其中必有一个全部是1的二进制值。从而证明如果没有重复，一定能够排序成功。另外通过这个反证法我们也可以知道，如果经过某一次排序后，二进制的最左边或者最右边出现了连续的1，比如 [1…1(m个)xxxx1…1(n个)] ，那么不论下一个序列是什么。这一个二进制最左边和最右边的1的个数是不会变少的。所以，第二个排序，从无序到有序的过程，实际上是，从两边向当中蔓延的过程。
不愧是哲学家
考古，好像第一个证明跟一个虫子那个挺像。