如何实现以下OrderElements功能？
char chars[] = {'a', 'b', 'c', 'd', 'e'};
int want_order[] = {2, 4, 3, 0, 1};
int length = 5;
OrderElements(chars, want_order, length);
// chars now contains: c, e, d, a, b
当您可以使用线性额外空间时很容易，但是否可以只使用恒定的额外空间来完成，即直接chars就地对元素进行排序？
PS：这不是考试题；我实际上需要这个功能。
澄清：似乎对所需的元素最终顺序存在误解。示例中的结果数组应具有以下元素，引用原始chars数组：
{chars[2], chars[4], chars[3], chars[0], chars[1]}
这是
{'c', 'e', 'd', 'a', 'b'}.
但严格来说，O(lg length)表示列表索引需要内存；但是，在本次讨论中，我将忽略这一点，因为使用 64 位i可能对于我们实际上可以重新排序的任何内容都足够大。
for (int i = 0; i < length; i++) {
int t = want_order[i];
while (t < i) {
// t has been moved already; we need to find out where the value that started there
// went. Since we must've put it at want_order[t] before, resume looking there
t = want_order[t];
// once t >= i, we know we've not touched that slot more than once, and so our
// value is there
}
swap(chars[i], chars[t]);
}
一个直观的解释：对于数组中的每一项，我们将目标值放入其中，将旧值存储在包含目标值的槽中。我们必须小心处理我们的目标价值被取代的情况；这是通过注意给定的插槽最多只交换两次来处理的；一次当其中的值被另一个值窃取时（这不可能发生，因为这次迭代会这样做）或者当值被替换以插入最终值时（这只发生在较低的索引上）。
这在您的示例数据上的外观说明：
i | want_order | chars | t
0 | 2 4 3 0 1 | a b c d e | 2 (swap)
1 | 2 4 3 0 1 | c b a d e | 4 (swap)
2 | 2 4 3 0 1 | c e d a b | 3 (swap)
3 | 2 4 3 0 1 | c e d a b | 0 (follow)
3 | 2 4 3 0 1 | c e d a b | 3 (swap - no-op)
4 | 2 4 3 0 1 | c e d a b | 1 (follow)
4 | 2 4 3 0 1 | c e d a b | 4 (swap - no-op)
该算法仅使用O(lg n)内存（用于索引），但我没有尝试完全分析它的运行时间。很明显，它是最坏的O(n^2)，但我怀疑它在实践中会比这更好。然而，它可能必须遵循的链的长度并没有真正的限制，因此原则上它实际上可能最终使用O(n^2)最坏情况输入的时间。
不可能的。
您至少需要 O(log (list size)) 才能知道已排序元素的索引。
上面的帖子有一个错误（它无意中覆盖了索引）。这是一个更正的版本：
char chars[] = {'a', 'b', 'c', 'd', 'e'};
int want_order[] = {2, 4, 3, 0, 1};
int length = 5;
OrderElements(chars, want_order, length) {
int i, j, k;
for(i = 0; i < length; ++i) {
if (want_order[i] == -1) continue;
j = startPos = want_order[i];
c = chars[i];
do {
swap(c, chars[j]);
k = want_order[j];
want_order[j] = -1;
j = k
} while(j != startPos);
}
}
这将在O(n²). 在外循环的每次迭代中，当前想要的元素被向下交换到它的正确位置（第一个内循环），然后调整剩余元素的想要的顺序以反映新的情况（第二个内循环）。
for (int i = 0; i < length; i++)
{
for (int j = wantedOrder[i]; j > i; j--)
{
Swap(chars, j, j - 1);
}
for (int j = i + 1; j < length; j++)
{
if (wantedOrder[j] < wantedOrder[i])
{
wantedOrder[j]++;
}
}
}
这当然需要破坏想要的订单数组。如果不允许这样做，我不知道如何解决问题（至少目前）。
如果允许更改 want_order 数组，则可以这样做。该算法相当简单，因为排列可以分解为循环。当您迭代一个循环时，只需标记每个正在访问的循环。时间复杂度为 O(N)。伪代码：
char chars[] = {'a', 'b', 'c', 'd', 'e'};
int want_order[] = {2, 4, 3, 0, 1};
int length = 5;
OrderElements(chars, want_order, length) {
int i, j, k;
for(i = 0; i < length; ++i) {
if (want_order[i] == -1) continue;
j = startPos = want_order[i];
c = chars[i];
do {
swap(c, chars[j]);
k = want_order[j];
want_order[j] = -1;
j = k
} while(j != startPos);
}
}
内存 O(1) 的排序操作是冒泡排序，但它的性能为 O(n²)