是否可以反转具有恒定额外空间的数组？

假设我有一个数组A with n系列中的独特元素[0, n)。换句话说，我有整数 [0, n) 的排列。

是否可以转型A into B使用 O(1) 额外空间（又名就地），这样B[A[i]] = 我?

例如：

       A                  B
[3, 1, 0, 2, 4] -> [2, 1, 3, 0, 4]

是的，这是可能的，使用 O(n^2) 时间算法：

获取索引 0 处的元素，然后将 0 写入该元素索引的单元格。然后使用刚刚覆盖的元素来获取下一个索引并在那里写入上一个索引。继续，直到回到索引 0。这是循环引导算法。

然后从索引 1, 2, ... 开始执行相同的操作，但在进行任何更改之前，请从该索引开始执行循环引导算法，而不进行任何修改。如果此循环包含低于起始索引的任何索引，则跳过它。

或者这个 O(n^3) 时间算法：

获取索引 0 处的元素，然后将 0 写入该元素索引的单元格。然后使用刚刚覆盖的元素来获取下一个索引并在那里写入上一个索引。继续，直到返回到索引 0。

然后从索引 1, 2, ... 开始执行相同的操作，但在进行任何更改之前，从所有前面的索引开始执行循环引导算法，而不进行任何修改。如果当前索引出现在任何先前的循环中，则跳过它。

我已经写了（稍微优化）执行 http://ideone.com/blO4u0C++11 中的 O(n^2) 算法，用于确定如果随机排列反转，每个元素平均需要多少次额外访问。结果如下：

size accesses
2^10 2.76172
2^12 4.77271
2^14 6.36212
2^16 7.10641
2^18 9.05811
2^20 10.3053
2^22 11.6851
2^24 12.6975
2^26 14.6125
2^28 16.0617

虽然大小呈指数增长，但元素访问的数量几乎呈线性增长，因此随机排列的预期时间复杂度类似于 O(n log n)。