你可以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