自頂向下非遞歸合併

我打算簡短地介紹一段相當大的一段代碼，我將以非遞歸方式說明一個特定函數，以說明一個觀點。我相信我已經確定了代碼的相應部分，即自頂向下非遞歸合併

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] [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個警告，當我編譯，但我認爲一旦我掌握了這些基礎，他們可能會自我解決。具體而言，「長」和「符號」這兩個術語分別在每個錯誤中丟失。

來源

2014-02-20 user3112563

這是錯誤的功能。嘗試找到像sort（Comparable []，Comparable []，Integer，Integer）''而不是。 –

您的第一個函數排序（Comparable []）不是遞歸的。第二個是 –

遞歸由一個函數自己調用的事實來表示，而不是有一些N-1。 'boolean abc（）{return abc（）; }'這個函數也是遞歸的。 –

據我瞭解，你想有非recadianive合併排序。查看它並將其調整爲您的代碼。

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

來源

2014-02-20 16:17:16 RMachnik

請提前通知我們，謝謝！ – RMachnik

自頂向下非遞歸合併

回答

相關問題