例如：[a,b,c,d,e,f] => [a,f].
我也将(另外)想要做相反的事情,首先使用奇数索引：
例如：[a,f] => [b,f,a,e].
我知道我可以创建单独的奇数/偶数数组然后重新合并它们,但性能是关键,我正在尝试找到一个单循环,就地解决方案,避免分配和使用临时数组.
语境：
我递归搜索一个移动的游戏树(带有alpha-beta的minimax)并且我正在尝试实现Lazy SMP,我在其他线程上搜索相同的位置,但尝试以略微不同的顺序移动,将结果保存到共享(换位) )表,以提高主搜索线程的效率.
澄清：
起始数组已经排序,我希望保持偶数/奇数索引内的顺序.也就是说,我不想只是将平均值和赔率分组在一起,最后说[f,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.我在下面添加了我的代码,但我不会将其标记为答案,因为它在技术上并不是我要求的.
解决方法
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,我们总是可以直接计算其目标索引
>从索引零开始,计算其目标索引,在此处移动项目,并从目标索引继续到下一个目标
>标记我们访问过的下半部分中的所有索引
>最终我们将看到我们所见过的指数;将最后一项放在那里,因为我们已经完成了这个循环
>从我们尚未访问过的下半部分找到下一个索引
>一旦我们耗尽了所有索引,我们就完成了
注意：如果重复运行此算法,您应该能够避免重新分配see []数组,方法是以最大大小分配一次,然后简单地用falses填充它.
