可以这样

来源: 于 2009-07-25 11:34:08 [博客] [旧帖] [给我悄悄话] 本文已被阅读：次

把你的算法改变一下：

纪录开始的位置为初始为止，最终位置为结束位置。
从A1开始，依次向右检查。
如果该数和初始位置不对应，跳过该数。
否则：纪录该数位置。从它开始，依次把数放到结束位置，并且把结束位置的数置换出来。检查结束位置是否为纪录，如果是则跳过（一个循环完成）

只要初始位置和结束位置计算时间是常数，这个算法就应该是线性时间，同时占用常数内存