你可以run一下這個程序，對任何n都適用

判斷是否排好可以用反函數g(k)，是O(1)。程序中已經實現了，不需要n為特殊的數。

謝謝你幫我解釋，這個程序就是這麽做的。很容易增加一些臨時變量數組驗證每個k最多隻被挪動一次。

“要檢查 x 的 loop 裏有沒有比 x 更小的位置”
這是不對的。隻要x沒排好，它就是loop裏最小的位置。換句話說，如果x不是loop裏最小位置（y是最小位置），那麽x已經在排y的時候排好了。

所有跟帖： 

• 你一直在假設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