java - 自顶向下、非递归合并

Question

关闭。这个问题需要多问 focused 。目前不接受答案。

---

想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post .

已关闭 9 年前。

Improve this question

我的目的是对一段相当大的代码进行简短的演示，其中我以非递归方式说明了一个特定的函数，以表明一个观点。我相信我已经确定了代码的适当部分，

public static void sort(Comparable[] a) {
        Comparable[] aux = new Comparable[a.length];
        sort(a, aux, 0, a.length-1);
        assert isSorted(a);

作为需要更改的代码部分。我没有看到的是如何真正使其成为非递归的。我知道我需要删除 a.length-1 部分，但我不知道删除什么。一位同事提到这比看起来更难，因为我需要保留原始代码的顺序。我不太明白他的意思，但我觉得包含这些信息也没什么坏处。

编辑:我在代码中找到了这个:

//使用辅助数组 aux[lo..hi] 对 a[lo..hi] 进行合并排序

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
    if (hi <= lo) return;
    int mid = lo + (hi - lo) / 2;
    sort(a, aux, lo, mid);
    sort(a, aux, mid + 1, hi);
    merge(a, aux, lo, mid, hi);
}

但是，我应该关注 public static void sort(Comparable[] a)根据我的提示。具体来说，我应该用新的非递归函数替换该函数。

编辑2:好的，如果我的第二个函数是递归函数，我该如何更改它？我认为当我看到类似 (N-1) 的东西时，那就意味着递归。但我在第二个函数中没有看到这一点。

编辑 3:到目前为止，帮助很大。我尝试合并下面给出的答案，并且在编译时遇到了这个问题:

File: /Users/spencer/Downloads/MergeTDNonrecursive.java  [line: 75]
Error: /Users/spencer/Downloads/MergeTDNonrecursive.java:75: possible loss of precision
found   : long
required: int

精度位的损失就是我迷失的地方，我以前从未见过这种情况。似乎是该错误来源的代码是:

if (rend > num) rend = num; 

我遇到的另一个错误是

File: /Users/spencer/Downloads/MergeTDNonrecursive.java  [line: 106]
Error: /Users/spencer/Downloads/MergeTDNonrecursive.java:106: cannot find symbol
symbol  : method sort(java.lang.Comparable[],java.lang.Comparable[],int,int)
location: class MergeTDNonrecursive

代码:sort(a, aux, 0, a.length-1);

我在编译时还收到了 2 个警告，但我认为一旦我涵盖了这些基础，它们可能会自行解决。具体来说，在每个错误中，我分别丢失了术语“long”和“symbol”。

Answer 1

据我了解，您希望进行非递归合并排序。查看它并使其适应您的代码。

float a[50000000],b[50000000];
void mergesort (long num)
{
    int rght, wid, rend;
    int i,j,m,t;

    for (int k=1; k < num; k *= 2 ) {       
        for (int left=0; left+k < num; left += k*2 ) {
            rght = left + k;        
            rend = rght + k;
            if (rend > num) rend = num; 
            m = left; i = left; j = rght; 
            while (i < rght && j < rend) { 
                if (a[i] <= a[j]) {         
                    b[m] = a[i]; i++;
                } else {
                    b[m] = a[j]; j++;
                }
                m++;
            }
            while (i < rght) { 
                b[m]=a[i]; 
                i++; m++;
            }
            while (j < rend) { 
                b[m]=a[j]; 
                j++; m++;
            }
            for (m=left; m < rend; m++) { 
                a[m] = b[m]; 
            }
        }
    }
}