Я застрял в реализации редиски Radix

Question

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

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

[23456, 24567],

мы хотим, чтобы сравнить 3 и 4, что приводит к 23456 < 24567.

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

Обратите внимание: Да, это вопрос, связанный с домашним заданием, поэтому я могу использовать здесь только примитивы. Мы не проходили через такие вещи, как math.pow (...). Заранее спасибо!

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

    if (numbers.length == 0) 
    return numbers; 

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

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

    for (i = 0; i < space[i].length; i++) { 
    sort(space[i], digit); //not sure how to work with digit here 
    } 

    return ... //not sure what to return here 

} 

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

} 

Answer 1

Чтобы извлечь последнюю цифру, оператор остаток % ваш друг:

123 % 10 == 3 

если вы не покрыли оператор %, то вы можете использовать

123 % 10 == 123 - (123/10 * 10) == 3 

К извлеките другую цифру, вы можете сначала переместить ее до конца с помощью /:

123/10 == 12 
12 % 10 == 2 

Поэтому вы можете извлечь произвольную цифру с помощью

(number/mask) % 10 

где маска ∈ {..., 10000, 1000, 100, 10, 1}.

Дополнительного кредит

Radix рода обычно реализуется в двоичной системе счисления, а не потому, что двоичный разряд (или последовательность их) может быть извлечена без выполнения разделения, который является более эффективным:

x % 16 == x & 15; 
x \ 16 == x >> 4; 

Кроме того, если вы реализуете это по-настоящему, вам понадобится более эффективный способ выращивания ведер (ваша реализация принимает O (n), чтобы добавить один элемент в ведро, добавив n элементов в ковш, поэтому берет O (n^2), что делает вашу сортировку radix медленнее, чем сортировка вставки).Dynamic arrays обычно реализуются с более эффективным geometric expansion.

Answer 2

Это должно работать:

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

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

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

     for (j = 0; j < numbers.length; j++) { 
      i = (numbers[j]/digit) % 10; 
      len[i]++; 
      for (int k = len[i] - 1; k > 0; k--) { 
       space[i][k] = space[i][k - 1]; 
      } 
      space[i][0] = 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; 

} 

а) Во-первых, space выделяется как имеющий только один столбец. Итак, space[i] = bucket не будет работать.

Вместо этого вы можете объявить его как int [10] [10]. (Примечание: оно поддерживает только 10 значений в одном ковше). Или вы можете выделять новые массивы программным способом. Или, конечно, лучше подходит List.

б) i = (numbers[j]/digit) % 10;

Чтобы получить только необходимую цифру. Например: если номер 12130 и digit = 1000, мы хотим установить i в 2, а не 12.

c) putInBucket заменен на место.

d) Для каждого bucket из space, мы сортируем его на одну цифру ниже, вызывая sort рекурсивно.

е) Наконец, результат должен быть возвращен (numbers), могут быть созданы с помощью цикла через space от цифры от 0 до 9.

Примечание: Это решение, вероятно, может быть лучше.