批处理程序的奇偶合并排序 [英] Batcher's odd-even-merge sort

问题描述

我有一个关于Batcher的奇偶合并排序的问题.我有以下代码:

Hi I have a question about Batcher's odd-even-merge sort. I have the following code:

public class Batcher {
  public static void batchsort(int a[], int l, int r) {
    int n = r-l+1;

    for (int p=1; p<n; p+=p)
      for (int k=p; k>0; k/=2)
        for (int j=k%p; j+k<n; j+=(k+k))
          for (int i=0; i<n-j-k; i++)
            if ((j+i)/(p+p) == (j+i+k)/(p+p))
              exch(a, l+j+i, l+j+i+k);
  }

  public static void main(String[] args) {
    int a[] = new int[] {2, 4, 3, 4, 6, 5, 3};

    batchsort(a, 0, a.length - 1);

    for (int i=0; i<a.length; i++) {
      System.out.println(a[i]);
    }
  }

  public static void exch(int a[], int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
  }
}

我将提供有关代码功能的一些注释:
它分为由变量p索引的阶段，最后一个阶段是p==n是批处理程序 odd-even-merge 时的下一个阶段是p==n/2是第一级和所有经过n/2的比较器消除了倒数第二个相位是当p==n/4与前两级的奇偶合并以及所有经过n/4的任何倍数的比较器消除了，依此类推

I will provide some comments about the code's function:
It's divided into phases indexed by variable p the last phase is when p==n is batchers odd-even-merge the next-to-phase is when p==n/2 is odd-even-merge with the first stage and all comparators that cross n/2 eliminated the third-to-last phase is when p==n/4 the odd-even-merge with the first two stages and all comparator that cross any multiple of n/4 eliminated and so forth.

结果是:

3
3
4
4
5
2
6

我错过了什么?
怎么了?

What have I missed?
What is wrong?

推荐答案

我不知道该算法，但是您需要在批量排序之前比较值，例如

I don't know the algorithm but you need to compare values in a in batchsort before switching them, e.g.

if ((j + i) / (p + p) == (j + i + k) / (p + p))
{
    if (a[l + j + i] > a[l + j + i + k])
    {
        exch(a, l + j + i, l + j + i + k);
    }
}

，或者如果您将临时变量用于组合索引，则可能更易读，例如

or that might be more readable if you use temp variables for the combined indices, e.g.

if ((j + i) / (p + p) == (j + i + k) / (p + p))
{
    int i1 = l + j + i;
    int i2 = l + j + i + k;
    if (a[i1] > a[i2])
    {
        exch(a, i1, i2);
    }
}

但是上面的评论者是对的-这的确写得不是很容易理解.您应该尝试确保相等的花括号具有相同的缩进，嵌套的for()的缩进大于其包含的for等，并且您可能还应该选择更多的描述性变量名.

but the commenters above are right - this really isn't written very readably at all. You should try to make sure that equal braces have the same indent, that nested for()s have more indent than their containing for, etc., and you should probably pick more descriptive variable names too.

这篇关于批处理程序的奇偶合并排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！