Как эта сортировка коллекции работает в java? - PullRequest
Новая
       37

Как эта сортировка коллекции работает в java?

0 голосов
/ 16 июня 2020

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

Вот фрагмент кода 

static void printLargest(List<String> arr){

    Collections.sort(arr, new Comparator<String>(){
        @Override
        public int compare(String X, String Y) {
            String XY=X + Y;
            String YX=Y + X;
            return XY.compareTo(YX) > 0 ? -1:1;
        }
    });

    Iterator it = arr.iterator();

    while(it.hasNext())
        System.out.print(it.next());
}

public static void main(String[] args) throws Exception {
   List<String> sample = new ArrayList<>();
   sample.add("34");
   sample.add("30");
   sample.add("9");
   sample.add("5");
   sample.add("3");

   printLargest(sample);
}

Если я правильно помню. Java Collection использует Quick Sort для сортировки входных данных.

Вот шаги отладчика:

  1. X = 30, Y = 34 , XY = 3034 , YX = 3430, return 1
  2. X = 9, Y = 30, XY = 930, YX = 309, return -1
  3. X = 9, Y = 30, XY = 930, YX = 309, return -1
  4. X= 9, Y = 34, XY = 934, YX = 349, return -1
  5. X = 5, Y = 34, XY = 534, YX = 345, return -1
  6. X = 9, Y = 5, XY = 59, YX = 95, return 1,
  7. X = 3, Y = 34, XY = 334, YX = 343, return 1,
  8. X = 3, Y= 30 , XY = 330, YX = 303, return -1

И на выходе будет 9534330. По сути, список изменился до 9, 5, 34, 3, 30. Если я вижу шаблон, я не могу понять, как они применяют Quick Sort здесь, на компараторе. Мне нужно немного разобраться в этом коде.

Любая подсказка будет заметна.

Изменить 1:

Если кто-то пропустил ссылку «Вопросы». Вот оно с рабочим решением:

https://www.geeksforgeeks.org/given-an-array-of-numbers-arrange-the-numbers-to-form-the-biggest-number/. (Ознакомьтесь с решением java)

1 Ответ

1 голос
/ 16 июня 2020

Это не сортировка отдельных чисел от наибольшего к наименьшему.

Но при этом данный список сортируется в таком порядке, что при добавлении последнего списка чисел будет получено наибольшее возможное число, которое может быть сделано путем добавления входных чисел.

Чтобы получить максимальное число, число (X) в списке должно появиться перед другим числом (Y) в списке, если число (X appended with Y, то есть XY = X + Y) больше числа (Y appended with X, то есть YX = Y + X). Поскольку XY и YX имеют одинаковую длину, сравнение чисел XY и YX может быть само по себе сравнением строк. Это то, что достигает 

new Comparator<String>(){
    @Override
    public int compare(String X, String Y) {
        String XY=X + Y;
        String YX=Y + X;
        return XY.compareTo(YX) > 0 ? -1:1;
    }
});

.

По вашему мнению, 

X = 30, Y = 34 , XY = 3034 , YX = 3430, return 1  --> this places 34 before 30

, потому что любая вероятность 34 *** 30 будет больше чем 30 *** 34 при условии, что мы исправим другие числа. 

X = 9, Y = 30,   XY = 930, YX = 309, return -1  --> this places 9 before 30

, потому что любая возможность 9 *** 30 будет больше, чем 30 *** 9 при условии, что мы исправим другие числа.

Мы можем распространить этот аргумент и на другие наблюдения.

...