Сортировка коллекции песен по времени выполнения - PullRequest
1 голос
/ 28 мая 2011

Я должен сделать программу, которая сортирует коллекцию песен по времени выполнения.Я должен проанализировать подборку песен, каждая из которых содержит строку «Заголовок», строку «Композитор» и целое число «Время выполнения».Вход будет передан через стандартный ввод, а вывод будет в стандартный вывод.

Вот пример ввода:

3
&
Pink Frost&Phillipps, Martin&234933
Se quel guerrier io fossi&Puccini, Giacomo&297539
Non piu andrai&Mozart&234933
M'appari tutt'amor&Flotow, F&252905

И вывод:

Se quel guerrier io fossi&Puccini, Giacomo&297539
M'appari tutt'amor&Flotow, F&252905
Non piu andrai&Mozart&234933

Я знаю, что у меня естьсортировать их по времени выполнения, но я не уверен, какой алгоритм сортировки использовать.Общеизвестно, что на ум приходят два алгоритма сортировки: сортировка слиянием и быстрая сортировка, потому что они кажутся самыми быстрыми в среднем.У меня также есть идея использовать Comparator для сравнения двух элементов времени выполнения в Коллекции.

Может кто-нибудь указать мне правильное направление?

Ответы [ 2 ]

1 голос
/ 28 мая 2011

Самый простой способ - написать класс для хранения вышеуказанных значений, который реализует интерфейс Comparable (или вы можете написать свой собственный Comparator). Метод compareTo может проверить время выполнения и соответственно вернуть значение.

Затем передайте его методу Collections.sort (). Этот метод использует оптимизированную версию Merge Sort. Вам не нужно писать собственную логику сортировки, чтобы справиться с этим, и вы можете положиться на платформу Java, чтобы сделать это за вас. Если вам не нужна особая настройка производительности метода сортировки, я думаю, это самый простой способ (KISS - Keep It Simple, Stupid).

Выдержка из Документов Java API на Collections.sort (http://download.oracle.com/javase/1,5.0/docs/api/java/util/Collections.html#sort%28java.util.List%29):

Алгоритм сортировки представляет собой модифицированную сортировку слиянием (в которой объединение опускается, если самый высокий элемент в нижнем подсписке меньше самого низкого элемента в верхнем подсписке). Этот алгоритм предлагает гарантированную производительность n log (n). Эта реализация сбрасывает указанный список в массив, сортирует массив и выполняет итерацию по списку, сбрасывая каждый элемент с соответствующей позиции в массиве. Это позволяет избежать производительности n2 log (n), которая может возникнуть в результате попытки отсортировать связанный список на месте.

0 голосов
/ 28 мая 2011

Просто придерживайтесь метода compareTo() для String или int (выполняется tittle) и используйте их в своих Comparator s.Далее - используйте Collections.sort(), который использует сортировку слиянием, что весьма неплохо:)

А, а во время выполнения вы должны добавить эти песни в список песен - ArrayList или LinkedList.И сортировать их по Collections.sort(yourListName, new yourComparatorName());

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...