Сортировка по имени

Question

У меня проблемы с сортировкой имен в алфавитном порядке с использованием сортировки по счетам, например, я полагаю, что сортировать в алфавитном порядке и добавить к нему, например, ввод числа 0001 Alex Smith, Gregory John, Alex Smith, Adam Richard, Alex Ryan, Вывод должен быть в следующем порядке:

Адам Ричард
Алекс Райан
Алекс Смит
Грегори Джон

Мой код до сих пор:

public class Names 
{
    //private static int[] c;

 public ArrayList<String> getUserInput()
{
        ArrayList<String> names = new ArrayList<String>(); 
    Scanner in = new Scanner(System.in);
    while (in.hasNext()) 
     {
         names.add(in.next());  
        System.out.println(names); 
     }
      in.close();
    return names;
}
 private static CountingSort(int A[], int B[], int k[])
{
    int i;
    int C[0];
    for(i = 0; i <= k; i++){
        C[i]=0;
    }

    for(int j=1; j <= A.length; ){
        C[A[j]] = C[A[j]] + 1;
    }//C[i] now contains numbers of elements equals to i
    for(int i=1; i < k; i++){
        C[i] = C[i] + C[i - 1];

    }
    for(int j = A.length; j--){
    B[C[A[j]]] = A[j];
    C[A[j]] = C[A[j]] - 1;   
   }
}
}

Answer 1

Подготовка данных

а. Сделайте длину каждой строки равной. Добавьте "*" в конце каждой строки, чтобы все длины были равны.

Modified Data — [‘a*’, ‘bd’, ‘cd’, ‘ab’, ‘bb’, ‘a*’, ‘cb’]

б. Преобразуйте эти измененные строки данных в числа, присвоив буквам позиционные значения. az до 1–26 и * до 0. Таким образом, это становится двумерным массивом.

Converted Data — [[1,0],[2,4],[3,4],[1,2],[2,2],[1,0],[3,2]]

Подсчет сортировки

1. Создать массив счетчиков из n измерений, где n= длина самой длинной строки (в данном случае 2), а количество столбцов в каждом измерении = максимальное значение в "Преобразованных данных" (в данном случае 4) +1(добавлено для '*'). Итак, создается счетный массив размером 5x5.

Например, если самая длинная строка равна 5, а самый высокий символ - "f", будет создан массив размером 7x7x7x7x7.

И, как и в обычном массиве счетчиков, храните значения на основе "преобразованных данных". Например, для [1,0] сохраняется значение 2. Массив подсчета

2. Накопите этот n-мерный массив, начиная с [0,0] до [4,4].

3. Теперь аналогичным образом используйте "Преобразованные данные" с массивом счетчиков, чтобы определить позицию каждой строки в отсортированном массиве. Например, - [1,0] (a*) позиция равна 2. И аналогично после определения позиции вычтите 1 из этого значения в массиве count. Таким образом, значение [1,0] в массиве Count становится равным 1. Точно так же позиция [2,4] (bd) равна 5 в отсортированном массиве.

https://playcode.io/475393

Answer 2

Подсчет сортировки - неправильный алгоритм сортировки для этой задачи. Алгоритм счетной сортировки предназначен для сортировки целочисленных значений в фиксированном диапазоне, поэтому его нельзя применять для сортировки строк.

С другой стороны, вы можете использовать основную сортировку для этой проблемы. Radix sort работает путем сортировки ввода по одной цифре или символу за раз, и она очень хорошо подходит для сортировки строк. Существует два основных вида сортировки по основанию: сортировка по значению с наиболее значащими цифрами и сортировка по знакам с наименьшими цифрами. Аспект MSD радикальной сортировки не слишком напоминает счетную сортировку, но LSD радикальная сортировка работает, используя сортировку по одному символу за раз. Если вы действительно должны использовать сортировку с подсчетом, я бы порекомендовал исследовать LSD-радикальную сортировку в качестве опции.