我在阅读一些StackOverflow问题时偶然发现了这个问题，但找不到令人满意的答案。
假设我们有一个长度n的array A以随机方式包含从0到n-1的索引。是否可以重新排列数组，使其结果A[ A[i] ]，并具有恒定的O(1)内存开销？
例：
A = [ 3, 2, 0, 1 ]
rearrange( A )
A = [ 1, 0, 3, 2 ]
如果可能的话，算法的轮廓会很好。否则解释为什么不可能。由于就地排序是一回事，因此可能其工作原理相似。
澄清： 如果没有内存约束，则算法很简单：
A = [ 3, 2, 0, 1 ]
A_r = Array_of_size( A )
for i = 0 to Arraysize - 1
A_r[ i ] = A[ A[i] ]
成果A_r = [ 1, 0, 3, 2]
这是可能的。
输入数组由作为同一数组中的索引的值组成，因此它是一个或多个循环的集合。每个循环可以有 1 个或多个元素。
数组的突变最好逐个周期地执行，因为一个周期中的更改只需要在该周期中临时存储一个值，而"下一个"值被复制到"上一个"插槽中，直到访问整个周期并且临时值可以放在最后一个插槽中。
要考虑的一件事是，在像这样突变的周期之后，它可能不会导致相同长度的周期。例如，如果一个周期的长度为 4，则突变将导致 2 个周期，每个周期 2 个值。更一般地说，长度均匀的循环将分为两个循环。奇数周期保持其长度，只是更改其顺序。
一旦一个周期发生了突变，算法就不应该"意外地"重新访问它的任何值，并将突变再次应用于该循环。
确保不会发生这种情况的一种方法是，仅在从左到右的迭代中访问其最右侧元素时将突变应用于循环。这是所提算法的关键。这样就可以确定这个循环中的元素永远不会再次被访问，也不会再次发生突变。
这是 JavaScript 中的一个实现。您可以在输入字段中输入数组值。每次更改输入时都会执行该算法：
function arrange(a) {
function isRightmostOfCycle(i) {
let j = a[i]
while (j < i) j = a[j]
return j == i
}
function updateCycle(i) {
let saved = a[i]
let k = i
for (let j = a[i]; j < i; j = a[j]) {
a[k] = a[j]
k = j
}
a[k] = saved
}
for (let i = 0; i < a.length; i++) {
if (isRightmostOfCycle(i)) updateCycle(i)
}
return a
}
// I/O handling
let input = document.querySelector("input")
let output = document.querySelector("pre");
(input.oninput = function () {
let a = (input.value.match(/d+/g) || []).map(Number)
// Check whether input is valid
let i = a.findIndex((_,i) => !a.includes(i))
output.textContent = i < 0 ? arrange(a) : "Missing " + i
})();input { width: 100% }Array values: <input value="2,0,5,7,6,4,1,8,3"><p>
Result:
<pre></pre>检查索引是否表示循环的最右侧元素的时间复杂度为 O(n)，因此总时间复杂度为O(n²)。然而，额外的空间复杂性是恒定的。
如果我们结合基于空洞的链交换，并且我们可以按数组中的最低或最高位置重新排列排列一个循环，这确实是可能的。我们只是针对每个仓位，只有当我们查看的仓位是该周期中最高的仓位时，我们才会在循环中链式进行链式。基于孔的方法确保我们只使用恒定空间来执行循环的旋转。缺点是时间复杂度变得O(n^2).这是一个简单的python实现：
def is_start(array, index):
start = index
index = array[index]
while start > index:
index = array[index]
return start == index
def rotate(array, index):
start = index
next = array[index]
hole = next
while start > next:
array[index] = array[next]
index = next
next = array[index]
array[index] = hole
def rearrange(array):
for index in range(len(array)):
if is_start(array, index):
rotate(array, index)
错误修复
(@trincot)指出，使用循环的最后一个条目而不是第一个条目可以确保我们永远不会调查可能损坏的循环。 效果：将不等式的分度从
start < index改为start > index。