以遞歸方式實現基數排序 - 如何在最後打印元素？

Question

注：

我已經問這個PROGRAMM before一個具體的問題，但現在我被困在最後一步，我想這可能會更好，打開一個新的線程它。

說明：

我需要實現的排序爲從0至99999遞歸一個PROGRAMM（這基本上是基數排序）。該過程本身有點類似於：用戶鍵入的數組中包含主方法中的這些數字。然後，主要方法調用排序方法，我創建了一個名爲'space'的具有10行和1列的二維數組。然後，我將數組中的每個數字除以數字，在第一次運行中將爲10.000。因此，例如，23456/10000 = 23456 = 2（在java中），因此，程序將這個數字放在空間[2] [0]中，所以在第二行。然後，我們把這整行和擴展它，這是在putInBucket方法中完成的。我們這樣做是爲了確保我們可以將另一個數字放入同一行。

我們爲「數字」數組內的每個數字執行此操作。然後，我們想要使用這些行並按照相同的原則重新排序它們，但現在我們來看看第二個數字。我們希望從左到右這樣做，而不是從右到左。所以，如果我們的第二行應該是這樣的

[23456，24567]，

我們會要比較的3和4。爲了做到這一點，我們在每次遞歸計算位數/ 10呼叫。如果數字爲0，則不需要再進行排序。

遞歸調用本身適用於從0到9的行，我們之前放入不同的數字，現在通過將它們放在不同的行中再次對它們進行排序。

問：

我覺得PROGRAMM做的事情是應該做的。不幸的是，我不知道如何正確打印結果。例如，在下面的代碼中，我試圖在main方法中打印出存儲桶，但它只給了我剛纔輸入的數組，所以這不可能是正確的。

我需要從第9行的所有元素開始，如果此行包含多個數字，我必須按照遞歸調用的結果對它們進行排序。

有沒有人有一個想法如何正確實施這個？提前致謝！

public static int[] sort(int[] numbers, int digit) { 

    if (numbers.length <= 1 || digits == 0) 
    return numbers; 

    int[][]space = new int[10][1]; 
    int i, j = 0; 

    for (j = 0; j < numbers.length; j++) { 
    i = numbers[j]/digit % 10; 
    space[i][0] = numbers[j]; 
    space[i] = putInBucket(space[i], numbers[j]); 
    } 

    digit = digit/10; 

    for (i = 0; i < 9; i++) { 
    sort(space[i], digit); 
    } 

    return numbers 

} 

private static int[] putInBucket(int[] bucket, int number) { 

    int[] bucket_new = new int[bucket.length+1]; 

    for (int i = 1; i < bucket_new.length; i++) { 
    bucket_new[i] = bucket[i-1]; 
    } 

    return bucket_new; 

} 

public static void main (String [] argv) { 

    int[] numbers = IO.readInts("Numbers: "); 
    int digit = 10000; 
    int[] bucket = sort(numbers, digit); 

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

} 

Answer 1

正如我在answer證明你前面的問題，你需要返回排序numbers。您可以通過從最小到最大的數字通過space獲得排序的數字。

int k = 0; 

    for (i = 0; i < 10; i++) { 
     for (j = 0; j < len[i]; j++) { 
      numbers[k] = space[i][j]; 
      k++; 
     } 
    } 

對於這一點，你可能需要跟蹤桶的長度的每個數字（在len[i]變量）。

完整的解決方案是：

public static int[] sort(int[] numbers, int digit) { 

    if (numbers.length == 0 || digit <= 0) 
      return numbers; 

    int[][]space = new int[10][1]; 
    int[] len = new int[10]; 
    int i, j = 0; 

     for (j = 0; j < numbers.length; j++) { 
      i = (numbers[j]/digit) % 10; 
      len[i]++; 
      space[i] = putInBucket(space[i], numbers[j]); 
     } 


     for (i = 0; i < 10; i++) { 
      int[] bucket = new int[len[i]]; 
      for (int k = 0; k < len[i]; k++) 
       bucket[k] = space[i][k]; 
      space[i] = sort(bucket, digit/10); 
     } 

     int k = 0; 

     for (i = 0; i < 10; i++) { 
      for (j = 0; j < len[i]; j++) { 
       numbers[k] = space[i][j]; 
       k++; 
      } 
     } 

     return numbers; 

} 

private static int[] putInBucket(int[] bucket, int number) { 

    int[] bucket_new = new int[bucket.length+1]; 


    for (int i = 1; i < bucket_new.length; i++) { 
     bucket_new[i] = bucket[i-1]; 
    } 
    bucket_new[0] = number; 

    return bucket_new; 

} 

Answer 2

在排序空間的本地實例被更新，但它返回輸入參數的數字，這是不被更新。

我在想空間應該初始化爲空間[10] [0]，因爲可能多一行空間不會有任何數據。

你確定這應該是一個從右到左（最低有效數字的第一個）基數排序？通常這是通過迭代完成的（只需將空間複製回每個外部循環的數字）。基數從左到右（最重要的數字在前）通常使用遞歸完成。

Bijay Gurung的排序（）可以有所簡化。在評論中所指出的變化：

public static int[] sort(int[] numbers, int digit) { 
    if (numbers.length == 0 || digit <= 0) 
     return numbers; 
    int[][]space = new int[10][0]; // [1] => [0] 
    int[] len = new int[10]; 
    int i, j; 
    for (j = 0; j < numbers.length; j++) { 
     i = (numbers[j]/digit) % 10; 
     len[i]++; 
     space[i] = putInBucket(space[i], numbers[j]); 
    } 
    for (i = 0; i < 10; i++) { 
    // int[] bucket = new int[len[i]];  // deleted 
    // for (int k = 0; k < len[i]; k++)  // deleted 
    //  bucket[k] = space[i][k];   // deleted 
     space[i] = sort(space[i], digit/10); // bucket => space[i] 
    } 
    int k = 0; 
    for (i = 0; i < 10; i++) { 
     for (j = 0; j < len[i]; j++) { 
      numbers[k] = space[i][j]; 
      k++; 
     } 
    } 
    return numbers; 
}