Реализация редискуляции Radix - как напечатать элементы в конце?

Question

Примечание:

я уже задал конкретный вопрос по этой программе before, но теперь я застрял на самом последнем этапе, и я предполагаю, что это могло бы быть лучше открыть новую тему для него.

Описание:

Я обязан осуществить программка, которая сортирует числа в диапазоне от 0 до 99999 рекурсивно (это в основном Radix сортировка). Сам процесс является своего рода simpel: пользователь вводит в массив, который содержит эти числа в основном методе. Затем основной метод вызывает метод sort, где я создаю двумерный массив с именем «space» с 10 строками и 1 столбец. Затем я делю каждое число в массиве на цифру, которая будет равна 10.000 в первом прогоне. Так, например, 23456/10000 = 2,3456 = 2 (в java), следовательно, программа помещает это число в космос [2] [0], поэтому во второй строке. Затем мы берем эту всю строку и расширяем ее, что делается в методе putInBucket. Мы делаем это, чтобы убедиться, что мы можем поместить другой номер в одну строку.

Мы делаем это для каждого числа, находящегося внутри массива 'numbers'. Затем мы хотим работать с этими строками и сортировать их по тому же принципу, но теперь посмотрим на вторую цифру. Мы хотим сделать это слева направо, а не справа налево. Так что, если наша вторая строка будет выглядеть следующим образом

[23456, 24567],

мы хотим, чтобы сравнить 3 и 4. Для того, чтобы сделать это, мы вычислим цифру/10 в каждом рекурсивном вызов. Если цифра равна 0, больше нечего сортировать.

Рекурсивный вызов сам по себе работает со строками от 0 до 9, где мы помещаем разные числа до и теперь сортируем их снова, помещая их в разные строки.

Вопрос:

Я думаю, что программа делает то, что он должен делать. К сожалению, я не знаю, как правильно печатать результат. Например, в приведенном ниже коде я попытался распечатать ведро в основном методе, но он только дает мне именно тот массив, который я только что напечатал, так что это невозможно.

Мне нужно начать со всех элементов в строке 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], так как возможно, что еще одна строка пространства не будет иметь никаких данных.

Вы уверены, что это должно быть справа налево (младшая значащая цифра вначале)? Обычно это делается с помощью итерации (просто скопируйте пространство обратно в числа в каждом внешнем цикле). Сортировка Radix слева направо (сначала самая значимая цифра) часто выполняется с помощью рекурсии.

Тип 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; 
}