AddInOrder Лучшая структура? Домашнее задание на Java

Question

В настоящее время у меня есть проблема, когда у меня есть список идентификаторов, каждый с соответствующим счетом.

Например:

ID: SCORE

1: 12

2: 15

3: 2

4: 99

Я хочу зациклить их и добавить их в структуру в порядке убывания баллов. Таким образом, результат будет выглядеть примерно так:

{4,2,1,3}

Каков наилучший способ сделать это на Java? Очередь?

Спасибо Philip

Answer 1

Я думаю, что сейчас самое время изучить интерфейс Comparable. Вы можете создать класс, который сравнивает по score и печатает его id при вызове toString(). Как упоминалось ранее, использование пользовательского Comparator также будет достаточно, но если вы никогда не работали с Comparable, я рекомендую сначала изучить его.

Вот ссылка на JavaDoc: http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Comparable.html

Вы должны знать, что для двух объектов o1 и o2 типа Comparable<T>, o1.compareTo(o2) вернет:

• -1, если o1
• 0, если o1 == o2 (опять же, в порядке, не обязательно равенство объектов)
• 1, если o1> o2

Эта информация поможет вам написать функцию compareTo в вашем пользовательском классе.

Как только вы написали свой класс, Java Collections класс предоставляет метод sort, который будет сортировать List из Comparables. Легко!

Вот ссылка для этого: http://java.sun.com/j2se/1.5.0/docs/api/java/util/Collections.html#sort%28java.util.List%29

Answer 2

Разве Collection.sort(list, comparator) не подходит?

(comparator - класс, реализующий Comparator и задающий логику сравнения)

(в качестве альтернативы ваш класс может реализовать интерфейс Comparable для внутренней логики сравнения)

Это не "AddInOrder", но он соответствует вашему требованию.

Answer 3

Вставьте элементы один за другим в отсортированный набор (например, набор деревьев ). Используйте класс для хранения id: score и напишите компаратор, который сравнивает два экземпляра этих классов на основе их оценки.

РЕДАКТИРОВАТЬ: увидел, что у вас уже есть список, в этом случае сортировка коллекции лучше.

Answer 4

Здесь есть несколько вариантов.Сортировка списка в конце может быть достаточной для ваших целей.

Если вы хотите убедиться, что инвариант порядка все время держится, то сортированный список / дерево - это путь.Java предоставляет класс PriorityQueue .

Однако в качестве детали реализации вам необходимо создать класс для инкапсуляции ID и Score и иметь класссравнимо с вашим выбором сортировки.