arrays - 就地数组重新排序？

假设我有一个长度为a的n数组和另一个长度为indices的数组n。 indices包含序列[0, n)的任意排列。我想按a指定的顺序重新排列indices。例如，使用D语法:

auto a = [8, 6, 7, 5, 3, 0, 9];
auto indices = [3, 6, 2, 4, 0, 1, 5];
reindexInPlace(a, indices);
assert(a == [5, 9, 7, 3, 8, 6, 0]);

是否可以在O(1)空间和O(n)时间中都做到这一点，最好不要改变indices？

最佳答案

随着indices的变异:( ..看起来很难(请参阅稳定的就地mergesort)。

a = [8, 6, 7, 5, 3, 0, 9]
indices = [3, 6, 2, 4, 0, 1, 5]

for i in xrange(len(a)):
    x = a[i]
    j = i
    while True:
        k = indices[j]
        indices[j] = j
        if k == i:
            break
        a[j] = a[k]
        j = k
    a[j] = x

print a

关于arrays - 就地数组重新排序？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7365814/