Java: обратная сортировка без сохранения порядка

Question

Обновление . Фактически, единственным приемлемым решением этой проблемы будет сортировка массива по возрастанию, а затем обратное его изменение.

Пусть S - следующая последовательность событий:

Event | Time
  A   | 0:00
  B   | 0:01
  C   | 0:01
  D   | 0:02

У меня есть простой компаратор для сортировки S , который сортирует элементы по значению time .

public int compare(Event e1, Event e2) {

    // Reverse sorting. 
    // _sortOrder is set outside this method.
    if(SORT_DESCENDING.equals(_sortOrder))
        return e2.getTime() - e1.getTime(); /* time is long */

    return e1.getTime() - e2.getTime();
}

Проблема в том, что при порядке сортировки по возрастанию S сортируется правильно: A, B, C, D.

Но когда я использую обратную сортировку, S становится D, B, C, A:

Event | Time
  D   | 0:02
  B   | 0:01 /* B and C should be reversed */
  C   | 0:01
  A   | 0:00

Это происходит потому, что алгоритм сортировки по умолчанию сохраняет исходный порядок для элементов с одинаковым значением time .

Итак, как мне отсортировать все наоборот, не сохраняя первоначальный порядок?

Примечание. Я знаю, что могу отсортировать S по возрастанию и просто вернуть его обратно, но, к сожалению, в моем случае это не вариант.

Answer 1

Алгоритм сортировки правильный: 0,01 - 0,01. Если есть что-то, что вы нам не говорите. Однако если вам нужен точный обратный порядок сортировки по возрастанию, сортируйте их в порядке возрастания и используйте Collections.reverse () . Под этим я подразумеваю:

List<SomeObject> list = ...;
Collections.sort(list, myComparator);
Collections.reverse(list);

который даст вам именно то, что вы хотите.

Но если задний ход не доступен, у вас осталось только два варианта:

<Ол>

Сделайте так, чтобы никакие два элемента не могли быть "равными". Либо включите другое поле, либо добавьте синтетическое (например, текущий индекс или первичный ключ, если это число). Это даст вам воспроизводимый, последовательный и зеркальный порядок; или

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

Теперь, прежде чем сказать, что вы не можете повернуть вспять (почему?), позвольте мне спросить вас, как вы сортируете? если вы используете Collections.sort () , рассмотрите исходный код (Java 6u10):

public static <T extends Comparable<? super T>> void sort(List<T> list) {
Object[] a = list.toArray();
Arrays.sort(a);
ListIterator<T> i = list.listIterator();
for (int j=0; j<a.length; j++) {
    i.next();
    i.set((T)a[j]);
}
}

Таким образом, он копирует коллекцию в массив, сортирует этот массив и затем использует его для изменения порядка коллекции.

Вы уверены, что не можете позволить себе разворот?

Answer 2

Что вы используете для сортировки? Я думаю, это то, что гарантирует стабильный вид - и у вас есть два равные значения, что касается сравнения.

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

РЕДАКТИРОВАТЬ: так как ваши данные не содержат никакой дополнительной информации о заказе, я не удивлюсь, если они были возвращены в разных заказах, когда вы снова выполнили тот же запрос в Oracle. Однако, если вы заботитесь только о порядке в этом конкретном случае, я предлагаю вам добавить дополнительное поле в представление Java в памяти для сохранения исходного индекса в загруженном списке - по мере чтения данных отслеживайте, сколько Вы прочитали и присвоили поле соответственно. Тогда вы можете использовать это при сортировке.

Answer 3

Я что-то упустил, или вы не могли просто использовать имя события (или что бы то ни было A, B, C и D) в качестве вторичного ключа сортировки? Просто расширьте ваш Comparator на что-то вроде:

public int compare(Event e1, Event e2) {
    int cmp = e1.getTime() - e2.getTime(); // compare times
    if (cmp == 0)  // if times are equal, compare names instead
        cmp = e1.getName().compareTo(e2.getName());
    return SORT_DESCENDING.equals(_sortOrder)? -cmp : cmp;
}

Answer 4

Я думаю, что вам действительно нужен вторичный критерий сортировки, так что вы можете сортировать элементы, даже если первичные критерии сортировки считают элементы равными. В вашем примере основным критерием будет время, а вторым - событие. Таким образом, вам не нужно полагаться на элементы в определенном порядке, прежде чем выполнять сортировку, что значительно упрощает процесс.

Если у вас действительно нет второстепенных критериев, вам, вероятно, придется поискать устойчивые и нестабильные алгоритмы сортировки, как упоминал Джон Скит.

Answer 5

Другой способ, но не решайте свою проблему.

List<SomeObject> list = ...;
Collections.sort(list, Collections.<SomeObject>reverseOrder());

Answer 6

Почему 0:01 меньше / больше 0:01 или почему они должны быть отсортированы особым образом, если они оба одинаковы?

Вы не ищете обратную сортировку, вы ищете обратную сортировку, извините. :)

Answer 7

Порядок сортировки выглядит правильно, просто сравните имена, если e1.getTime () == e2.getTime ().

Answer 8

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