是否可以在内存开销不变的情况下重新排列数组？

Question

在阅读一些StackOverflow问题时，我偶然发现了这个问题，但是找不到令人满意的答案。

假设我们有一个array Alength ，以随机方式n包含其索引，从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]

Answer 1

有可能的。

输入数组由作为同一数组中索引的值组成，因此它是一个或多个循环的集合。每个周期可以包含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²）。然而，额外的空间复杂度是恒定的。