0

假设我们有这个整数数组称为data

 3
 2
 4
 5
 2

此外，我们还有以下相同大小的数组，称为info

 1
 4
 0
 2
 3

的每个值info代表第一个数组上的一个索引。因此，例如第一个值是1这意味着0最终排序数组的位置将具有值data[info[0]]。

按照这个逻辑，最终的排序数组将如下：

data[info[0]] => 2
data[info[1]] => 2
data[info[2]] => 3
data[info[3]] => 4
data[info[4]] => 5

我想对数组进行就地排序data，而不使用任何额外的大小内存，N其中数组N的大小是data多少。此外，我希望总操作量尽可能小。

我一直在想办法解决我的问题，但是我想不出任何不使用额外内存的东西。请记住，这些是我自己对我正在实施的系统的限制，如果不能保留这些限制，那么我可能不得不考虑其他事情。

任何想法，将不胜感激。

先感谢您

4

2 回答 2

2

为什么不简单

for i in 0..n-1 : 
   info[i] := data[info[i]]

现在info保存已排序的数组。如果它必须在 中data，只需将其复制回来，下一步：

for i in 0..n-1 : 
    data[i] := info[i]

2*n副本，总体而言。

于 2013-04-30T15:25:15.223 回答
1

如果info数组不需要保持完整，您可以将其用作额外的存储并排序O(n)：

for(int i = 0; i < n; ++i) {
    int where = info[i];
    if (where == i) continue;
    info[i] = data[i];
    data[i] = i < where ? data[where] : info[where];
}

如果 的元素data已经在正确的位置，我们跳过该索引。否则，记住info数组中的元素，并将正确的元素写入，如果它来自较大的索引，则从其中data获取它，如果它来自较小的索引，则从其中获取。datainfo

当然，这种简单的方法要求info和data数组的类型相同，并且通常会3*n复制。

如果data元素不能存储在info数组中，我们可以遵循以下循环info：

for(int i = 0; i < n; ++i) {
    // Check if this is already in the right place, if so mark as done
    if (info[i] == i) info[i] = -1;

    // Nothing to do if we already treated this index
    if (info[i] < 0) continue;

    // New cycle we haven't treated yet
    Stuff temp = data[i];    // remember value
    int j = info[i], k = i;
    while(j != i) {
        // copy the right value into data[k]
        data[k] = data[j];
        // mark index k as done
        info[k] = -1;
        // get next indices
        k = j;
        j = info[j];
    }
    // Now close the cycle
    data[k] = temp;
    info[k] = -1;
}

这会n - F + C复制data元素，其中F是已经在正确位置的元素的数量（排序排列的固定点），并且C是排序排列中长度的循环数> 1。这意味着副本的数量最多为3*n/2.

于 2013-04-29T21:48:10.100 回答