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

Question

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

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

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

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

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 сортируется правильно: А, В, С, D.

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

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

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

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

Примечание: Я знаю, что могу сортировать 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

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

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

Answer 3

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

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

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

Answer 4

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

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

Answer 5

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

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 6

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

Answer 7

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

Answer 8

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

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