我有一个已排序的数组,我想重新排序,以便以前偶数索引的项目在开头,然后是奇数索引的项目。

例如: [a, b, c, d, e, f] => [a, c, e, b, d, f]

我也(单独)想做相反的事情,首先使用奇数索引:

例如: [a, b, c, d, e, f] => [b, d, f, a, c, e]

我知道我可以创建单独的奇数/偶数数组,然后重新合并它们,但性能是关键,我正在尝试找到避免分配和使用临时数组的单循环就地解决方案。

语境:

我正在递归搜索移动游戏树(带 alpha-beta 的极小值)并尝试实现 Lazy SMP,我在其他线程上搜索相同的位置,但尝试以稍微不同的顺序移动,将结果保存到共享(换位) ) 表,以提高主搜索线程的效率。

说明:

起始数组已经排序,我希望保持偶数/奇数索引中的顺序。即,我不想只是将偶数和赔率组合在一起并最终说 [f, b, d, e, c, a]

此外,我严格按照索引值排序,而不是存储在那里的项目。因此,任何涉及对项目值进行搜索谓词的方法都将不起作用。

虽然我是用 C# 编写的,但我不想使用 LINQ,因为我需要将代码移植到没有 LINQ 的系统中。

我希望有一种方法可以遍历数组一次并执行一系列项目交换,这样我最终会得到我所描述的排序。我一直在纸上尝试,但还没有得到任何工作。

说明二:

我用字母而不是数字更新了示例,并在将它们倒退时交换了奇数/偶数示例。我两个都想要。

最终,我试图模拟循环遍历原始数组,但跳过所有其他项目并仍在查看每个项目。对于两个循环,我会执行以下操作:

// Case 1: Regular order
for (int i = 0; i < items.Length; i ++)
{
    // Process
}


// Case 2: Even indexes first
for (int i = 0; i < items.Length; i += 2)
{
    // Process
}

for (int i = 1; i < items.Length; i += 2)
{
    // Process
}


// Case 3: Odd indexes first
for (int i = 1; i < items.Length; i += 2)
{
    // Process
}

for (int i = 0; i < items.Length; i += 2)
{
    // Process
}

循环内的处理足够复杂,因为它递归地调用此函数,具有用于提前终止循环的单独条件等,因此我不想复制它和/或将它放在另一个函数中。

因此,与其有两个循环,或者一个处理所有三种情况的复杂循环,我宁愿只是对项目进行预排序。

说明 3:

我需要处理所有三种情况的东西,支持任何大小的数组(不仅仅是项目数),并且不会使游戏搜索循环内容困惑。我认为在该循环之前进行就地预排序是最好的选择。

最后,我决定放弃就地预排序并使用跳过项目的自定义迭代器扩展 List。我在下面添加了我的代码,但我不会将其标记为答案,因为它在技术上不是我所要求的。

谢谢大家的帮助。 (如果有人确实发布了一个循环,基于就地交换的解决方案,适用于任意数量的项目,我会很高兴接受它作为答案。)

最佳答案

这是一个算法,它在数组的单个路径中执行此操作。它假设数组有偶数个项目 N ,并且我们可以分配 bool[N/2] 数组:

static void OddEvenSwap(int[] data) {
    int n = data.Length / 2;
    int p = 0;
    var seen = new bool[n];
    while (true) {
        int last = data[p];
        do {
            var tmp = data[p];
            data[p] = last;
            last = tmp;
            if (p < n) {
                seen[p] = true;
            }
            p = (p/2) + (p%2 == 0 ? n : 0);
        } while (p >= n || !seen[p]);
        data[p] = last;
        while (p != n && seen[p]) {
            p++;
        }
        if (p == n) {
            break;
        }
    }
}

以下是其工作原理的简要说明:
  • 给定一个项目的源索引 p,我们总是可以直接计算它的目标索引
  • 从索引 0 开始,计算其目标索引,将项目移到那里,然后从目标索引继续到下一个目标
  • 标记我们访问过的下半部分的所有索引
  • 最终我们会回到我们看到的索引;将最后一项放在那里,因为我们已经完成了循环
  • 从我们还没有访问过的下半部分找到下一个索引
  • 一旦我们用完所有索引,我们就完成了

  • Demo.

    注意: 如果你重复运行这个算法,你应该能够通过以最大大小分配一次 seen[] 数组,然后简单地用 false 填充它来避免重新分配 ojit_code 数组。

    关于c# - 如何就地重新排序数组以将偶数索引项放在奇数之前?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/49618039/

    10-11 23:11
    查看更多