Вопрос не указывает, как обрабатывать отрицательные целые числа в лексикографическом порядке сортировки. Строковые методы, представленные ранее, обычно сортируют отрицательные значения на фронте; например, {-123, -345, 0, 234, 78} будут оставлены в этом порядке. Но если знаки минус должны были быть проигнорированы, порядок вывода должен быть {0, -123, 234, -345, 78}. Можно адаптировать строковый метод для создания этого порядка с помощью нескольких громоздких дополнительных тестов.
Может быть проще, как в теории, так и в коде, использовать компаратор, который сравнивает дробные части общих логарифмов двух целых чисел. То есть, он будет сравнивать мантиссы логарифмов базы 10 двух чисел. Компаратор на основе логарифма будет работать быстрее или медленнее, чем линейный компаратор, в зависимости от характеристик производительности с плавающей запятой процессора и качества реализации.
Код java, показанный в конце этого ответа, включает в себя два компаратора на основе логарифма: alogCompare
и slogCompare
. Первый игнорирует знаки, поэтому будет производить {0, -123, 234, -345, 78} из {-123, -345, 0, 234, 78}.
Числовые группы, показанные ниже, являются выходными данными программы Java.
В разделе «dar rand» показан массив случайных данных dar
как сгенерированный. Он читает поперек, а затем вниз, по 5 элементов в строке. Примечание: массивы sar
, lara
и lars
первоначально являются несортированными копиями dar
.
Раздел «dar sort» - dar
после сортировки по Arrays.sort(dar);
.
В разделе «сар закон» показывает массив sar
после сортировки с Arrays.sort(sar,lexCompare);
, где lexCompare
похож на Comparator
показанный в ответ Джейсон Коэна.
В разделе «лар с журнала» показывает массив lars
после сортировки по Arrays.sort(lars,slogCompare);
, иллюстрирующая способ логарифм основе, что дает тот же порядок, как это делают lexCompare
и другие методы на основе строки.
В разделе «lar a log» показан массив lara
после сортировки по Arrays.sort(lara,alogCompare);
, иллюстрирующий метод на основе логарифма, который игнорирует знаки минус.
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
Код Java приведен ниже.
// 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");
}
}
Зачем вам нужна нулевая площадка? –
О, нулевое заполнение требуется только в том случае, если я делаю сортировку радикса (надеюсь, что я не ошибаюсь), потому что это проще. В нем я просто рассматриваю конкретную позицию каждого целого числа во время итерации. Если я сделаю простой «strcmp», я думаю, это не потребуется. – Skylark
На самом деле, если вы делаете сортировку radix с s [0], тогда вам не нужно прокладывать. –