如何在给定目标索引数组的情况下对数组进行排序？

How would you sort a given array arr in-place given an array of target indices ind?

在给定目标索引数组的情况下，如何对给定的数组arr进行排序？

For example:

例如：

var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [ 4,   0,   5,   2,   1,   3 ];

rearrange(arr, ind);

console.log(arr); // => ["B", "E", "D", "F", "A", "C"]

arr = ["A", "B", "C", "D"];
ind = [ 2,   3,   1,   0 ];

rearrange(arr, ind);

console.log(arr); // => ["D", "C", "A", "B"]

I tried the following algorithm, but it fails on the second example above.

我尝试了以下算法，但它在上面的第二个例子中失败了。

function swap(arr, i, k) {
  var temp = arr[i];
  arr[i] = arr[k];
  arr[k] = temp;
}

function rearrange(arr, ind) {
  for (var i = 0, len = arr.length; i < len; i++) {
    if (ind[i] !== i) {
      swap(arr, i, ind[i]);
      swap(ind, i, ind[i]);
    }
  }
}

How would you solve this in O(n) time and O(1) extra space?

你如何在O（n）时间和O（1）额外空间中解决这个问题？

Could you provide a proof that your algorithm works?

你能提供一个证明你的算法有效吗？

---

Note: This question looks similar to this one, but here mutating ind is allowed.

注意：这个问题与此问题类似，但这里允许变异ind。

7 个解决方案

#1

The algorithm fails because it has only one loop over the indices of your list.

该算法失败，因为它只有一个循环覆盖列表的索引。

What happens in your algorithm is this :

你的算法会发生什么：

i=0 -> ["A", "B", "C", "D"] , [ 2,   3,   1,   0 ]
i=1 -> ["C", "B", "A", "D"] , [ 1,   3,   2,   0 ]
i=2 -> ["C", "D", "A", "B"] , [ 1,   0,   2,   3 ]
i=3 -> ["C", "D", "A", "B"] , [ 1,   0,   2,   3 ]

Note how by the first swap, 1 is in position 0 and you will not visit it again unless you swap it with 0, which does not happen in this example.

请注意，通过第一次交换，1位于位置0，除非您将其与0交换，否则不会再次访问它，这在此示例中不会发生。

What your algorithm misses is an internal loop that runs through sub-cycles of indexes. Try replacing the if by while in rearrange:

您的算法遗漏的是一个内部循环，它贯穿索引的子循环。尝试在重新排列时替换if by：

function rearrange(arr, ind) {
   for (var i = 0, len = arr.length; i < len; i++) {
      while (ind[i] !== i) {
         swap(arr, i, ind[i]);
         swap(ind, i, ind[i]);
      }
   }
}

Note on complexity: although this is a double loop, complexity does not change because at each swap, one element is correctly placed, and each element is read at most twice (once through the cycling, once though the for loop).

关于复杂性的注意事项：虽然这是一个双循环，但复杂性不会改变，因为在每次交换时，一个元素被正确放置，并且每个元素最多读取两次（一次通过循环，一次通过for循环）。

Note on proof: I will not do a complete proof of this algorithm here, but I can give leads. If ind is a permutation, then all elements belong to closed permutative sub-cycles. The while loop ensures that you're iterating entire cycles, the for loop ensures that you're checking for every possible cycle.

关于证明的注意事项：我不会在这里完整地证明这个算法，但我可以给出引导。如果ind是置换，则所有元素都属于闭合的置换子循环。 while循环确保您迭代整个循环，for循环确保您检查每个可能的循环。

#2

I suggest to swap until the same index is reached and then take the next outer index.

我建议交换，直到达到相同的索引，然后采取下一个外部索引。

function swap(arr, i, k) {
    var temp = arr[i];
    arr[i] = arr[k];
    arr[k] = temp;
}

function rearrange(arr, ind) {
    var i = arr.length;
    while (i--) {
        while (ind[i] !== i) {
            swap(arr, i, ind[i]);
            swap(ind, i, ind[i]);
        }
    }
}

var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [ 4,   0,   5,   2,   1,   3 ];

rearrange(arr, ind);
console.log(arr); // => ["B", "E", "D", "F", "A", "C"]

arr = ["A", "B", "C", "D"];
ind = [ 2,   3,   1,   0 ];

rearrange(arr, ind);
console.log(arr); // => ["D", "C", "A", "B"];

#3

How would you solve this in O(n) time?

你会在O（n）时间内如何解决这个问题？

By simply using a temporary array and iterating the arrays twice, you can reduce it to O(n)

通过简单地使用临时数组并迭代数组两次，您可以将其减少到O（n）

function rearrange(arr, ind) 
{
  var temp = [], len = arr.length;
  //first re-arrange in a new array
  for(var counter = 0; counter < len; counter++)
  {
     temp[ind[counter]] = arr[counter];
  }  
  //copy the values as per new indices from temp
  for(var counter = 0; counter < len; counter++)
  {
     arr[counter] = temp[counter];
  }  
}

#4

I suggest that you return your result in a new array

我建议你将结果返回到一个新数组中

   function createArray(arr, ind) {
        var result = [];
        for (var i = 0, len = arr.length; i < len; i++) {
            result.push(arr[ind[i]]);
        }
        return result;
    }

This is in O(n) time

这是在O（n）时间

var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];
console.log(createArray(arr,ind))

#5

There is a lot of discussion on a similar problem In-place array reordering?

关于类似问题的地方数组重新排序有很多讨论？

The difference is that in original problem ind[i] is a required index for element arr[i], while in the similar problem i is a required index for element arr[ind[i]]

区别在于原始问题ind [i]是元素arr [i]的必需索引，而在类似问题中，i是元素arr [ind [i]]的必需索引

Going back to the original algorithm, a working alternative may be

回到原始算法，一个可行的替代方案可能是

function swap(arr, i, k) {
  var temp = arr[i];
  arr[i] = arr[k];
  arr[k] = temp;
}

function rearrange(arr, ind) {
  for (var i = 0, len = arr.length; i < len; i++) {
    if (ind[i] !== i) {
      swap(arr, i, ind[i]);
      swap(ind, i, ind[i]);
      if (ind[i] < i) {
        i = ind[i]-1;
      }
    }
  }
}

It's still O(1) space, but it makes redundant checks and may be more complex than O(n)

它仍然是O（1）空间，但它进行冗余检查，可能比O（n）更复杂

#6

If you satisfied with doing that with less complexity method, then there is a one:

如果您对复杂性较低的方法表示满意，那么有一个：

• Make a new array with length equal to arr length and with empty objects
• 创建一个长度等于arr长度和空对象的新数组
• splice the new array by the index of ind[i], remove 1 object , and replace it with arr[i]
• 通过ind [i]的索引拼接新数组，删除1个对象，并用arr [i]替换它
• Equalize the old array(arr) with the new one
• 使旧的数组（arr）均衡

window.onload = function () {
    
    'use strict'; 
	
	var arr = ["A", "B", "C", "D", "E", "F"];
	var ind = [ 4,   0,   3,   2,   1,   5 ];
	var temp = [];

	for (var i = 0; i < arr.length; i++) {
	    temp[i] = '';
	}

	for (var v = 0; v < arr.length; v++) {
	    temp.splice(ind[v], 1, arr[v]);
	}
	
	arr = temp;
	console.log(arr);
};

#7

It's a bit faster to "rotate" the cycles rather than use swaps. C example:

“旋转”周期而不是使用交换更快一些。 C示例：

    // reorder A in place according to sorted indices in I
    // tA is temp value for A
    for(i = 0; i < n; i++){
        if(i != I[i]){
            tA = A[i];
            k = i;
            while(i != (j = I[k])){
                A[k] = A[j];
                I[k] = k;
                k = j;
            }
            A[k] = tA;
            I[k] = k;
        }
    }