Реализация Radix sort в java - немало вопросов

Question

Хотя это не ясно указано в моем упражнении, я должен реализовать рекурсивно Radix sort. К сожалению, я работал над этой задачей несколько дней, но, к сожалению, мне удалось получить мусор. Мы должны работать с двумя методами. Метод sort получает определенный массив с числами от 0 до 999 и цифрой, на которую мы смотрим. Мы должны создать двумерную матрицу здесь, чтобы распределить числа внутри массива. Так, например, 523 позиционируется в пятом ряду, а 27 позиционируется в 0-й строке, так как он интерпретируется как 027.

Я попытался сделать это с помощью конструкции switch-case, деля цифры внутри массива на 100, проверяя остаток, а затем поместите число относительно остатка. Затем я как-то попытался создать ведра, которые включают только числа с одинаковой цифрой, поэтому, например, 237 и 247 будут выброшены в одно и то же ведро в первом «раунде». Я попытался сделать это, взяв целую строку «полей» -матрицы, где мы ввели значения ранее.

В методе putInBucket мне необходимо расширить ведро (что я и сделал правильно, я думаю), а затем вернул его.

Извините, я знаю, что код является полным мусором, но, возможно, есть кто-то, кто понимает, что я делаю, и могу немного помочь мне.

Я просто не вижу, как мне нужно работать с ведрами здесь, я даже не понимаю, почему я должен их расширять, и я не вижу способа вернуть его методу сортировки (что, я думаю, я должен делать).

Дополнительное описание:

Все это призвано работать следующим образом: Берем массив целых чисел в диапазоне от 0 до 999. Каждый номер сортируется по первой цифре, как уже упоминалось выше. Представьте, что у вас есть ведра, обозначенные цифрами от 0 до 9. Вы начинаете сортировку, помещая 523 в ведро 5, 672 в ведро 6 и так далее. Это легко, когда в одном из ковшей есть только одно число (или вообще не число). Но это становится сложнее (и именно здесь может возникнуть рекурсия), когда вы хотите поставить более одного номера в одном ковше. Механизм теперь выглядит следующим образом: мы помещаем два числа с одинаковой первой цифрой в одном ковше, например 237 и 245. Теперь мы хотим отсортировать эти числа снова по тому же алгоритму, то есть мы называем метод sort (каким-то образом) снова с массивом, который содержит только эти два числа и сортирует их снова, но теперь мы делаем, глядя на вторую цифру, поэтому мы будем сравнивать 3 и 4. Мы сортируем каждое число внутри массива, как это, и в конце, чтобы получить отсортированный массив, мы начинаем в конце, то есть в ведро 9, а затем просто складываем все вместе. Если бы мы были в ведре 2, алгоритм заглянул бы в рекурсивный шаг и уже получил отсортированный массив [237, 245] и доставил бы его, чтобы завершить все это.

Мои собственные проблемы:

Я не понимаю, почему мы должны степени ведро, и я не могу понять из описания. Просто сказано, что мы должны это делать. Я бы предположил, что мы хотим, чтобы он копировал в нем еще один элемент, потому что, если у нас есть ведра от 0 до 9, размещение двух чисел внутри одного и того же ведра означает только то, что мы перезапишем первое значение. Это может быть причиной того, что нам нужно вернуть новое расширенное ведро, но я не уверен в этом. Кроме того, я не знаю, как идти дальше оттуда. Даже если у меня есть расширенное ведро, это не так, как будто я могу просто привязать его к старой матрице и снова скопировать в нее еще один элемент.

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

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

    int[][] fields = new int[10][array.length]; 
    int[] bucket = new int[array.length]; 
    int i = 0; 

    for (int j = 0; j < array.length; j++) { 
    switch (array[j]/100) { 

    case 0: i = 0; break; 
    case 1: i = 1; break; 

    ... 

    } 

    fields[i][j] = array[j] 
    bucket[i] = fields[i][j]; 
    } 
    return bucket; 
    } 

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

    int[] bucket_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[] array = readInts("Please type in the numbers: "); 
    int digit = 0; 
    int[] bucket = sort(array, digit); 
    } 

Answer 1

• Вы не можете использовать цифры в то, что это довольно подозрительно
• Переключатель/корпус выглядит довольно извилистый путь, чтобы написать i = array[j] / 100
• Я бы рекомендовал прочитать описание википедии о радиальная сортировка.
• Выражение для извлечения цифры из базового номера 10: (number / Math.pow(10, digit)) % 10.
• Обратите внимание, что вы можете считать цифры слева направо или справа налево, убедитесь, что вы это правильно.
• Я предполагаю, что сначала вы хотите отсортировать цифру 0, затем для цифры 1, затем для цифры 2. Поэтому в конце сортировки должен быть рекурсивный вызов, который делает это.
• Ваш массив ведер должен быть двумерным. Вам нужно будет назвать это так: buckets[i] = putInBucket(buckets[i], array[j]). Если вы обрабатываете null в putInBuckets, вам не нужно его инициализировать.
• Причина, по которой вам нужен массив 2d bucket и putInBucket (вместо поля фиксированного размера), заключается в том, что вы не знаете, сколько чисел будет указано в каждом ковше.
• Вторая фаза (чтение из ковшей в массив) отсутствует перед рекурсивным вызовом
• убедитесь, чтобы остановить рекурсию после 3-х цифр

Успехов