algorithm - Batcher 的奇偶合并排序

Question

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

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 是 batchers odd-even-merge next-to-阶段是当 p==n/2 与第一阶段奇偶合并并且所有跨越 n/2 的比较器消除时倒数第三阶段是 p== n/4 与前两个阶段的奇偶合并和所有跨越 n/4 的任何倍数的比较器被消除等等。

结果是:

3
3
4
4
5
2
6

我错过了什么？
怎么了？

Answer 1

我不知道算法，但你需要在切换它们之前比较 in batchsort 中的值，例如

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);
    }
}

或者如果您对组合索引使用临时变量，这可能更具可读性，例如

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 等的缩进更多，并且您也应该选择更具描述性的变量名称。