LSD Radix codice Sort in java
-
26-09-2019 - |
Domanda
Sto Montanti per un esame che sarà di circa algoritmi di ordinamento. Un amico mi ha dato questo codice su LSD ordinamento digitale, e non capisco il motivo per cui lui sta usando i numeri 96,97 e 64? Ho letto un paio di cose su digitale LSD tipo, ma non ho capito come funziona.
public class LSDRadix {
private static String[] list;
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.nextLine().trim());
int size=0;
list =new String[n];
for(int i=0; i<n; i++){
list[i]= sc.nextLine();
if(size < list[i].length()){
size = list[i].length();
}
}
sort(size);
for(int j=0; j<n;j++)
System.out.println(list[j]);
}
private static void sort(int sizes){
int numChars = 58;
String [] aux = new String[list.length];
int[] counter;
for(int i=sizes-1; i>=0 ;i--){
counter = new int[numChars];
for(int j=0; j<list.length; j++){
if(list[j].length() > i){
if(list[j].charAt(i) >= 97)
counter[list[j].charAt(i)-96]++;
else
counter[list[j].charAt(i)-64]++;
}else{
counter[0]++;
}
}
for(int j=0; j<numChars-1; j++){
counter[j+1] += counter[j];
}
for(int j=list.length-1; j>=0; j--){
if(list[j].length() > i){
int pos;
if(list[j].charAt(i) >= 97){
pos = list[j].charAt(i)-96;
}else{
pos = list[j].charAt(i)-64;
}
aux[counter[pos]-1] = list[j];
counter[pos]--;
}else{
aux[counter[0]-1] = list[j];
counter[0]--;
}
}
for(int j=0; j<list.length; j++){
list[j] = aux[j];
}
}
}
}
Soluzione
97 è il valore ASCII per la lettera 'a'. Se il carattere in prova è una lettera minuscola, sottraendo 96 dal suo valore ASCII darà un numero compreso tra 1 e 26.
In caso contrario, il carattere viene considerata una lettera maiuscola. 65 è il valore ASCII per la lettera 'A', quindi sottraendo 64 sarà nuovamente invia un valore tra 1 e 26.
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow