如何在适当的位置重新排序数组以将偶数索引项放在奇数之前？

问题描述 投票：6回答：7

我有一个排序数组，我想重新排序，以便先前甚至索引的项目在开头，然后是奇数索引项目。

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

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

c# algorithm smp
7个回答
5
投票

这是一种在阵列上的单个路径中执行的算法。它假设数组具有偶数个项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[]数组，方法是在最大大小分配一次，然后用falses填充它。

2
投票

最终我试图模拟循环原始数组，但跳过所有其他项目仍然查看每个项目。

在这种情况下，您根本不需要排序：使用专门的步进器函数，在偶数索引之前遍历奇数索引，反之亦然。

这种方法适用于N的任何偶数值（数组的长度）。

int N = 28;
Console.WriteLine("Odd before even");
for (var i = 1 ; i != N ; i = (i + 2) % (N+1)) {
    Console.Write("{0} ", i);
}
Console.WriteLine("Even before odd");
for (var i = 1 ; i != N ; i = (i + 2) % (N+1)) {
    // The formula is a bit complicated to avoid ternary:
    Console.Write("{0} ", -2*(i%2)+i+1);
}

Demo.

1
投票

使用LINQ对数组进行排序很容易。要按奇数/偶数排序，只需从您提供给i % 2的谓词中返回基于OrderBy()的值。

var list = new int[] { 1, 2, 3, 4, 5, 6 };
var sorted = list.OrderBy( i => i % 2 );
Console.WriteLine(string.Join(",",sorted));

输出：

2,4,6,1,3,5

如果你需要sorted作为一个数组，只需添加ToArray()：

var list = new int[] { 1, 2, 3, 4, 5, 6 };
var sorted = list.OrderBy( i => i % 2 ).ToArray();
Console.WriteLine(string.Join(",",sorted));

如果你需要更新原始数组（“就地”），你可以将它复制回数组，如下所示：

var list = new int[] { 1, 2, 3, 4, 5, 6 };
var sorted = list.OrderBy( i => i % 2 );
sorted.Select( (n, i) => list[i] = n ).Last();
Console.WriteLine(string.Join(",",list));

请注意，此解决方案需要对原始数组进行排序。如果不是，您可以使用额外的LINQ调用添加排序步骤：

var list = new int[] { 6, 5, 4, 3, 2, 1 };
var sorted = list.OrderBy( i => i).OrderBy( i => i % 2 );
sorted.Select( (n, i) => list[i] = n ).Last();
Console.WriteLine(string.Join(",",list));
1
投票

这结果是一个非常有趣的问题。首先注意到O（N ^ 2）的一个简单解决方案已经发布，所以现在的问题是我们是否可以做得更好。

到目前为止我最好的尝试：只需将赔率和平均值扔到你想要的位置，然后对每个半数组进行排序。

static void swap<t>(ref T a, ref T b) {
    var temp = a;
    a = b;
    b = a;
}
static void ThrowInHalf<T>(T[] arr) {
    for (var i = 0 ; i < arr.Length/2; i+=2) {
        swap(arr[i],arr[L/2+i+1];
    }
}

排序后所有的平均值应该在下半场，而赔率在第一位。问题就解决了，你得到了完全相同的问题 - 即使子数组的索引需要在奇数之前，所以你可以再次运行算法，依此类推，每次运行半个数组，一个经典的O（ nlog n）。当然，您可以按照相同的运行时间成本对每个半数组进行重新排序（在c#中不像其他语言那样直接，但是there are options）。

线性时间的其他尝试

我尝试了两件事，但我被困了。首先：

static void sortAttempt1<T>(T[] array) {
    for(var i=0,inc=1; i+inc<array.Length; ++i) {
        swap(array[i],array[i+inc]);
        ++inc;
    }
}

这将是你想要的上半场。我还没有确定一种算法方法来看看如何重新排序后半部分，但它看起来几乎就像你可以计算出一个结构，并取决于2的幂是数组的长度。

第二次尝试（我看到的这个版本最初是由dasblinkenlight发布的）：

static int next(int i) {
    if(i&1)
        return i/2;
    return (L+i)/2;
}
static int cycle<T>(T[] array,int start) {
    var perms = 0;
    var keep  = array[start];
    var n     = next(start);
    while(n  != start) {
        swap(array[n],keep);
        n = next(n);
        ++perms;
    }
    return perms;
}
void sortAttempt2<T>(T[] array) {
    int perms = 0;
    for(int start = 0; perms<array.Length-1; start+=2) {
        perms += cycle(array,start);
    }
}

此解决方案在阵列上运行循环。例如：

0,1,2,3,4,5,6,7,8

从索引0开始，将数据准确放置在您想要的位置，然后将您刚删除的内容放在您想要的位置，依此类推，直到您关闭一个圆圈（next函数告诉我们索引的确切位置） ：

0->4->6->7->3->1->0

这样你得到：

1,3,2,7,0,5,4,6,8

现在从索引2开始运行一个循环（仍然存在）

2->5->2

我们想要在O（n）中排序。问题是找到从哪里开始下一个周期。 start+2工作到一个长度为21的数组，但在增加的输入量开始失败之后。我无法在空间和时间中找到O（1）解决方案来获得一般情况的下一次迭代。

我的总结

  1. 解决这个问题至少可以在O（nlog n）时间内完成。
  2. 我在初始解决方案中再提供了两次尝试。

任何有想法的人都会非常感激他们。当然包括时间下限的证明。注意严格禁止分配大小依赖于N的数组。

0
投票

您可以尝试这一点，对于具有一百万个元素的数组，它几乎是OrderBy / ToArray的3倍。

for (int i = 0; i < masiv.Length; i++)
        {
            if (i % 2 != 0) //or if (i % 2 == 0)
            {
                int j = i / 2;
                int tmp = masiv[i];
                masiv[i] = masiv[j];
                masiv[j] = tmp;
            }
        }
QuickSort(masiv, masiv.Length / 2, masiv.Length - 1);

//Quicksort method
public static void QuickSort(int[] a, int start, int end)
    {
        if (start >= end)
        {
            return;
        }

        int num = a[start];

        int i = start, j = end;

        while (i < j)
        {
            while (i < j && a[j] > num)
            {
                j--;
            }

            a[i] = a[j];

            while (i < j && a[i] < num)
            {
                i++;
            }

            a[j] = a[i];
        }

        a[i] = num;
        QuickSort(a, start, i - 1);
        QuickSort(a, i + 1, end);
    }
0
投票

这将做一个就地排序：

static void SortOddEven<T>(T[] source)
{
    for (var start = 0; start < source.Length; start++)
    {
        for (var swap = start; swap < source.Length - start - 1; swap += 2)
        {
            var temp = source[swap];
            source[swap] = source[swap + 1];
            source[swap + 1] = temp;
        }
    }
}

相应的奇偶排序基本相同：

static void SortEvenOdd<T>(T[] source)
{
    for (var start = 1; start < source.Length; start++)
    {
        for (var swap = start; swap < source.Length - start; swap += 2)
        {
            var temp = source[swap];
            source[swap] = source[swap + 1];
            source[swap + 1] = temp;
        }
    }
}
0
投票

在澄清中，我说我正在寻找的最终结果是一种在跳过其他项目时进行迭代的方法。

我假设一个就地排序将是更快/更清洁的方法，但最后我最终扩展List像这样：

static class ListExtensions
{
    public static IEnumerable<T> GetEnumerableByOrderType<T>(this List<T> items, OrderType orderType)
    {
       int i = orderType == OrderType.SkipOffset && items.Count > 1 ? 1 : 0;

        int count = 0;
        while (i < items.Count)
        {
            yield return items[i];

            count++;

            i += orderType == OrderType.Default ? 1 : 2;

            if (count < items.Count && i >= items.Count)
            {
                i = orderType == OrderType.SkipOffset ? 0 : 1;
            }
        }
    }
}

public enum OrderType
{
    Default = 0,
    Skip, // Starts at 0
    SkipOffset // Starts at 1
}

然后我就可以简单地改变：

List<Move> moves = GetSortedMoves();
foreach (Move in moves)
{
    // Processing
}

至：

List<Move> moves = GetSortedMoves();
foreach (Move in moves.GetEnumerableByOrderType(OrderType.Skip))
{
    // Processing
}

它适用于所有三种排序类型和任何大小的List。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.