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);

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

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

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

Теперь, прежде чем сказать, что вы не можете повернуть вспять (почему?), Позвольте мне спросить вас, как вы сортируете? если вы используете 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

Другой способ, но не решить вашу проблему:

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

Answer 4

Я что-то упустил, или вы не могли просто использовать имя события (или каковы 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 5

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

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

Answer 6

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

Answer 7

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

Answer 8

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

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