如何使用 O(1) 辅助空间将数组排列成给定顺序？

Question

如何实现以下 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'}. 

Answer 1

但严格来说，表示列表索引需要 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) 时间。

Answer 2

不可能的。

您至少需要 O(log (列表大小)) 才能知道已排序元素的索引。

Answer 3

这将在 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]++;
        }
    }
}

这当然需要销毁想要的订单数组。如果这是不允许的，我不知道如何解决问题（至少目前如此）。

Answer 4

上面的帖子有一个错误（它无意中覆盖了索引）。这是一个更正的版本：

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);
  }
}

Answer 5

如果允许更改 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);
  }
}

Answer 6

使用内存的排序操作 O(1) 是冒泡排序，但它的性能为 O(n²)

http:// en.wikipedia.org/wiki/Bubble_sort