La pregunta no indica cómo tratar enteros negativos en el orden de clasificación lexicográfica. Los métodos basados en cadenas presentados anteriormente normalmente ordenarán los valores negativos al frente; por ejemplo, {-123, -345, 0, 234, 78} quedaría en ese orden. Pero si se suponía que los signos negativos debían ignorarse, la orden de salida debería ser {0, -123, 234, -345, 78}. Uno podría adaptar un método basado en cuerdas para producir ese orden mediante pruebas adicionales algo engorrosas.
Puede ser más simple, tanto en teoría como en código, usar un comparador que compare partes fraccionarias de logaritmos comunes de dos enteros. Es decir, comparará las mantisas de los logaritmos de la base 10 de dos números. Un comparador basado en logaritmos se ejecutará más rápido o más lento que un comparador basado en cadenas, dependiendo de las especificaciones de rendimiento de coma flotante de una CPU y de la calidad de las implementaciones.
El código java que se muestra al final de esta respuesta incluye dos comparadores basados en logaritmos: alogCompare
y slogCompare
. El primero ignora los signos, por lo que produciría {0, -123, 234, -345, 78} de {-123, -345, 0, 234, 78}.
Los grupos de números que se muestran a continuación son los resultados producidos por el programa java.
La sección "dar rand" muestra una matriz de datos aleatorios dar
según se haya generado. Lee a lo ancho y luego abajo, 5 elementos por línea. Tenga en cuenta que las matrices sar
, lara
y lars
inicialmente son copias sin clasificar de dar
.
La sección "dar sort" es dar
después de ordenar por Arrays.sort(dar);
.
La sección “sar lex” muestra array sar
después de la clasificación con Arrays.sort(sar,lexCompare);
, donde lexCompare
es similar a la Comparator
se muestra en la respuesta de Jason Cohen.
La sección “lar s registro” muestra array lars
después de la clasificación por Arrays.sort(lars,slogCompare);
, que ilustra un método basado en el logaritmo que da el mismo orden que hacer lexCompare
y otros métodos basados en cadenas.
La sección "lar a log" muestra la matriz lara
después de ordenar por Arrays.sort(lara,alogCompare);
, lo que ilustra un método basado en logaritmos que ignora los signos menos.
dar rand -335768 115776 -9576 185484 81528
dar rand 79300 0 3128 4095 -69377
dar rand -67584 9900 -50568 -162792 70992
dar sort -335768 -162792 -69377 -67584 -50568
dar sort -9576 0 3128 4095 9900
dar sort 70992 79300 81528 115776 185484
sar lex -162792 -335768 -50568 -67584 -69377
sar lex -9576 0 115776 185484 3128
sar lex 4095 70992 79300 81528 9900
lar s log -162792 -335768 -50568 -67584 -69377
lar s log -9576 0 115776 185484 3128
lar s log 4095 70992 79300 81528 9900
lar a log 0 115776 -162792 185484 3128
lar a log -335768 4095 -50568 -67584 -69377
lar a log 70992 79300 81528 -9576 9900
El código de Java se muestra a continuación.
// Code for "How can I sort numbers lexicographically?" - jw - 2 Jul 2014
import java.util.Random;
import java.util.Comparator;
import java.lang.Math;
import java.util.Arrays;
public class lex882954 {
// Comparator from Jason Cohen's answer
public static Comparator<Integer> lexCompare = new Comparator<Integer>(){
public int compare(Integer x, Integer y) {
return x.toString().compareTo(y.toString());
}
};
// Comparator that uses "abs." logarithms of numbers instead of strings
public static Comparator<Integer> alogCompare = new Comparator<Integer>(){
public int compare(Integer x, Integer y) {
Double xl = (x==0)? 0 : Math.log10(Math.abs(x));
Double yl = (y==0)? 0 : Math.log10(Math.abs(y));
Double xf=xl-xl.intValue();
return xf.compareTo(yl-yl.intValue());
}
};
// Comparator that uses "signed" logarithms of numbers instead of strings
public static Comparator<Integer> slogCompare = new Comparator<Integer>(){
public int compare(Integer x, Integer y) {
Double xl = (x==0)? 0 : Math.log10(Math.abs(x));
Double yl = (y==0)? 0 : Math.log10(Math.abs(y));
Double xf=xl-xl.intValue()+Integer.signum(x);
return xf.compareTo(yl-yl.intValue()+Integer.signum(y));
}
};
// Print array before or after sorting
public static void printArr(Integer[] ar, int asize, String aname) {
int j;
for(j=0; j < asize; ++j) {
if (j%5==0)
System.out.printf("%n%8s ", aname);
System.out.printf(" %9d", ar[j]);
}
System.out.println();
}
// Main Program -- to test comparators
public static void main(String[] args) {
int j, dasize=15, hir=99;
Random rnd = new Random(12345);
Integer[] dar = new Integer[dasize];
Integer[] sar = new Integer[dasize];
Integer[] lara = new Integer[dasize];
Integer[] lars = new Integer[dasize];
for(j=0; j < dasize; ++j) {
lara[j] = lars[j] = sar[j] = dar[j] = rnd.nextInt(hir) *
rnd.nextInt(hir) * (rnd.nextInt(hir)-44);
}
printArr(dar, dasize, "dar rand");
Arrays.sort(dar);
printArr(dar, dasize, "dar sort");
Arrays.sort(sar, lexCompare);
printArr(sar, dasize, "sar lex");
Arrays.sort(lars, slogCompare);
printArr(lars, dasize, "lar s log");
Arrays.sort(lara, alogCompare);
printArr(lara, dasize, "lar a log");
}
}
¿Por qué necesita cero almohadilla? –
Oh, el relleno de cero es obligatorio solo si hago una ordenación de radix (espero no estar equivocándome) porque es más fácil de esa manera. En él, simplemente examino una posición particular de cada número entero durante una iteración. Si hago un simple 'strcmp', supongo que no será necesario. – Skylark
En realidad, si está haciendo una ordenación por radix desde s [0], entonces no necesita rellenar. –