书的排序
http://www.matrix67.com/blog/archives/3066/comment-page-1
????書架的某一層里放了一套百科全書，但它們排列的順序卻是亂的。一個傻子想要把這套書排好順序，也就是說他想要書架里的書從左至右分別是第 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 為循環中被挪到右邊的書中卷號最大的一本，矛盾就產生了。
總結
