我有一个已排序的数组,我想重新排序,以便以前偶数索引的项目在开头,然后是奇数索引的项目。
例如: [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
,我们总是可以直接计算它的目标索引 Demo.
注意: 如果你重复运行这个算法,你应该能够通过以最大大小分配一次
seen[]
数组,然后简单地用 false
填充它来避免重新分配 ojit_code 数组。关于c# - 如何就地重新排序数组以将偶数索引项放在奇数之前?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/49618039/