c# - 如何就地重新排序数组以将偶数索引项放在奇数之前？

Question

我有一个已排序的数组，我想重新排序，使之前的偶数索引项位于开头，然后是奇数索引项。

例如:[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 的 minimax)并尝试实现 Lazy SMP，在其中我在其他线程上搜索相同的位置但尝试以稍微不同的顺序移动，将结果保存到共享(转置)表，以提高主搜索线程的效率。

说明:

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

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

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

我希望有一种方法可以循环遍历数组一次并执行一系列项目交换，这样我就可以得到我所描述的排序。我一直在纸上尝试，但还没有任何效果。

说明2:

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

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

// 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。我在下面添加了我的代码，但我不会将其标记为答案，因为它在技术上不是我要求的。

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

Answer 1

这是一个算法，它在数组上的单个路径中执行此操作。它假设数组有偶数个项目 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，我们总是可以直接计算它的目标索引
• 从索引零开始，计算其目标索引，将项目移到那里，然后从目标索引继续到下一个目标
• 标记我们访问过的下半部分的所有索引
• 最终我们会回到我们所看到的索引；将最后一项放在那里，因为我们已经完成了循环
• 从我们还没有访问过的下半部分找到下一个索引
• 一旦我们用尽了所有索引，我们就完成了

Demo.

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