Сортировка по наименее значащей цифре

Question

Я пытаюсь написать программу, которая принимает массив из пяти четырехзначных чисел и сортирует массив, основанный на наименее значащей цифре. Например, если числа были 1234, 5432, 4567 и 8978, массив сортировался сначала по последней цифре, поэтому сортировка гнезда была бы 5432, 1224, 4597, 8978. Затем после этого было бы 1224, 5432, 8978, 4597. И так далее, пока он не будет полностью отсортирован.

Я написал код для отображения массива и его части для сортировки. Я не уверен, как написать уравнения, которые мне нужны, чтобы сравнить каждую цифру. Это мой код для сортировки по каждой цифре:

public static void sortByDigit(int[] array, int size) 
    { 
    for(int i = 0; i < size; i++) 
    { 
     for(int j = 0; j < size; j++) 
     { 


     } 

     for(i = 0; i < size; i++) 
     { 
     System.out.println(array[i]); 
     } 
    } 
    } 

Я не уверен, что положить в петлю вложенного цикла. Я думаю, мне нужно использовать модуль.

Я просто написал это, чтобы отделить цифры, но я не знаю, как поменять номера или сравнить их.

int first = array[i]%10; 
    int second = (array[i]%100)/10; 
    int third = (array[i]%1000)/10; 
    int fourth = (array[i]%10000)/10; 

Будет ли это идти в цикле for?

Answer 1

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

Ваша догадка, что вам нужен модуль, абсолютно правильный. Оператор modulo (%) возвращает остаток по заданной операции деления. Это означает, что значение 10 % 2 равно 0, так как остатка нет. 10 % 3, однако, даст 1, так как остаток равен единице.

Учитывая, что быстрый фон по модулю, нам просто нужно выяснить, как сделать метод, который может захватить цифру. Давайте начнем с общей подписью:

public int getValueAtIdx(int value, int idx){ 
} 

Таким образом, если мы называем getValueAtIdx(145, 2), он должен вернуть 1 (при условии, что индекс начинается с младшего разряда). Если мы позвоним getValueAtIdx(562354, 3), он должен вернуть 2. Вы поняли.

Хорошо, давайте начнем с выяснения, как это сделать в простом случае. Скажем, мы звоним getValueAtIdx(27, 0). Используя модуль, мы должны уметь захватить 7. Наше уравнение равно 27 % x = 7, и нам просто нужно определить x. Итак, 27 делится на то, что даст нам остаток от 7? 10, конечно! Это делает наше уравнение 27 % 10 = 7.

Теперь это все нахожу и денди, но как 10 относится к 0? Ну, давайте попробуем и возьмем значение по индексу 1 на этот раз (2) и посмотрим, не получится ли это выяснить. С тем, что мы делали в прошлый раз, у нас должно было быть что-то вроде 27 % x = 27 (ПРЕДУПРЕЖДЕНИЕ: здесь есть кролик-дыра, где вы могли бы подумать, что x должно быть 5, но при дальнейшем рассмотрении можно найти, что работает только в этом случае). Что, если мы возьмем 10, который мы использовали ранее, но положим квадрат (index+1)? Это даст нам 27 % 100 = 27. Тогда все, что нам нужно сделать, это разделить на 10, и мы хороши.

Так что это будет выглядеть в функции, которую мы создаем?

public int getValueAtIdx(int value, int idx){ 
    int modDivisor = (int) Math.pow(10, (idx+1)); 
    int remainder = value % modDivisor; 
    int digit  = remainder/(modDivisor/10); 
    return digit; 
} 

Итак, давайте, чтобы вернуться к более сложному примеру: getValueAtIdx(562354, 3).

На первом этапе modDivisor становится 10^4, что равно 10000.

На втором этапе remainder установлен в 562354 % 10000, что равно 2354.

На третьем и последнем этапе digit установлен на remainder/(10000/10). Разрушая это, получаем remainder/1000, который (с использованием целочисленного деления) равен 2.

Наш последний шаг - это возвращаемая цифра, которую мы приобрели.

EDIT: Что касается собственно логики сортировки, вы можете посмотреть here за хорошую идею.

Общий процесс состоит в том, чтобы сравнить две цифры и, если они равны, перейти к следующей цифре. Если они не равны, поместите их в ведро и двигайтесь дальше.