static <T> void arrange(T[] data, int[] p) {
boolean[] done = new boolean[p.length];
for (int i = 0; i < p.length; i++) {
if (!done[i]) {
T t = data[i];
for (int j = i;;) {
done[j] = true;
if (p[j] != i) {
data[j] = data[p[j]];
j = p[j];
} else {
data[j] = t;
break;
}
}
}
}
}
done。done。我假设您可以承受每个元素额外的一个比特位，因为您似乎愿意使用排列数组，而排列数组的大小是其几倍。p是一个临时数组，你可以用它来代替done数组 - 只需在数据[i]处于正确位置时将p[i]设置为-1（或其他一些哨兵值）。 - Mark Ransom如果您不介意为额外的索引散列表分配内存，您可以保留原始位置到当前位置的映射，以获得接近O(n)的时间复杂度。这是一个Ruby示例，因为它易于阅读且类似于伪代码。（这可能可以更短或更符合Ruby习惯用语，但我已经写出来了以便清晰明了。）
#!/usr/bin/ruby
objects = ['d', 'e', 'a', 'c', 'b']
order = [2, 4, 3, 0, 1]
cur_locations = {}
order.each_with_index do |orig_location, ordinality|
# Find the current location of the item.
cur_location = orig_location
while not cur_locations[cur_location].nil? do
cur_location = cur_locations[cur_location]
end
# Swap the items and keep track of whatever we swapped forward.
objects[ordinality], objects[cur_location] = objects[cur_location], objects[ordinality]
cur_locations[ordinality] = orig_location
end
puts objects.join(' ')
这显然需要一些额外的哈希内存，但由于它仅用于索引而不是您的“相当大”的对象，希望这是可以接受的。由于哈希查找是O(1)，即使由于一个项目已经向前交换了多次并且您必须多次重写cur_location而导致复杂度略微增加，但整个算法应该相对接近O(n)。
如果您想要提前构建原始位置到当前位置的完整哈希表，或者保留当前位置到原始位置的反向哈希表，并稍微修改算法以将其降至严格的O(n)，那么也可以。这会更加复杂并占用更多空间，因此这是我编写的版本，但修改不应该很困难。
编辑：实际上，我相当确定时间复杂度只是O(n)，因为每个序数最多只能有一个关联的跳跃，因此最大查找次数限制为n。
#!/usr/bin/env python
def rearrange(objects, permutation):
"""Rearrange `objects` inplace according to `permutation`.
``result = [objects[p] for p in permutation]``
"""
seen = [False] * len(permutation)
for i, already_seen in enumerate(seen):
if not already_seen: # start permutation cycle
first_obj, j = objects[i], i
while True:
seen[j] = True
p = permutation[j]
if p == i: # end permutation cycle
objects[j] = first_obj # [old] p -> j
break
objects[j], j = objects[p], p # p -> j
我写完后注意到，这个算法与@meriton's answer in Java中的算法相同。
以下是代码的test函数：
def test():
import itertools
N = 9
for perm in itertools.permutations(range(N)):
L = range(N)
LL = L[:]
rearrange(L, perm)
assert L == [LL[i] for i in perm] == list(perm), (L, list(perm), LL)
# test whether assertions are enabled
try:
assert 0
except AssertionError:
pass
else:
raise RuntimeError("assertions must be enabled for the test")
if __name__ == "__main__":
test()
有一个直方图排序算法，虽然运行时间稍微比O(N) (N log log n)高一点。
我可以使用O(N)的空间来完成它——将其复制到新数组中，然后再复制回来。
编辑：我知道有一种算法可以进行操作。这个想法是在整数1..N的数组上执行交换，同时在你的大对象数组上镜像交换。我现在只是找不到这个算法。
这个问题是在最小化O(1)额外存储的情况下应用置换的问题：“原地置换”。
它是可以解决的，但是事先并不明显。
它在Knuth的练习中简要描述，并且为了工作我必须解密它并弄清楚它是如何工作的。请看5.2＃13。
关于这个问题的一些更现代的工作，带有伪代码：
我最终为此编写了一个不同的算法，它首先生成一个交换列表以应用顺序，然后运行交换以应用它。优点是，如果您将排序应用于多个列表，则可以重复使用交换列表，因为交换算法非常简单。
void make_swaps(vector<int> order, vector<pair<int,int>> &swaps)
{
// order[0] is the index in the old list of the new list's first value.
// Invert the mapping: inverse[0] is the index in the new list of the
// old list's first value.
vector<int> inverse(order.size());
for(int i = 0; i < order.size(); ++i)
inverse[order[i]] = i;
swaps.resize(0);
for(int idx1 = 0; idx1 < order.size(); ++idx1)
{
// Swap list[idx] with list[order[idx]], and record this swap.
int idx2 = order[idx1];
if(idx1 == idx2)
continue;
swaps.push_back(make_pair(idx1, idx2));
// list[idx1] is now in the correct place, but whoever wanted the value we moved out
// of idx2 now needs to look in its new position.
int idx1_dep = inverse[idx1];
order[idx1_dep] = idx2;
inverse[idx2] = idx1_dep;
}
}
template<typename T>
void run_swaps(T data, const vector<pair<int,int>> &swaps)
{
for(const auto &s: swaps)
{
int src = s.first;
int dst = s.second;
swap(data[src], data[dst]);
}
}
void test()
{
vector<int> order = { 2, 3, 1, 4, 0 };
vector<pair<int,int>> swaps;
make_swaps(order, swaps);
vector<string> data = { "a", "b", "c", "d", "e" };
run_swaps(data, swaps);
}