主要是難以判斷一個位置有沒有排好。

一種想法是從小到大排，每次把一個loop 裏的排好，然後排下一個位置 x 的時候， 要檢查 x 的 loop 裏有沒有比 x 更小的位置， 如果有， x 應該已經排好了； 如果沒有，就排 x 這個 loop. 這個算法的問題是不一定能在常數時間內檢查 x 的 loop 裏有沒有比 x 更小的位置。

n 為比較特殊的數，比如 2^m， 或者 2^m -1， 的時候, 似乎這個檢測相對簡單.

所有跟帖： 

• 你可以run一下這個程序，對任何n都適用 -說了就走- ♂ (357 bytes) () 07/30/2009 postreply 20:47:50

• 你一直在假設a[k]=k。沒有這個假設你的算法不成立 -康MM- ♀ (0 bytes) () 07/31/2009 postreply 07:14:51

• 那麽請問你的假設是什麽？ -說了就走- ♂ (216 bytes) () 07/31/2009 postreply 18:16:46

• 還是問冬瓜太郎吧，他說可以就可以 -康MM- ♀ (177 bytes) () 08/02/2009 postreply 10:25:52

• 你說得很有道理 -說了就走- ♂ (2675 bytes) () 08/02/2009 postreply 13:50:02

• 我還是覺得我們在說兩件不同的事 -康MM- ♀ (0 bytes) () 08/06/2009 postreply 17:49:24