Головоломка сортировки списка

Question

Предполагая, что у меня есть

final Iterable<String> unsorted = asList("FOO", "BAR", "PREFA", "ZOO", "PREFZ", "PREFOO");

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

[PREFZ, PREFA, BAR, FOO, PREFOO, ZOO]

(список, который начинается с известных значений, которые должны появиться первыми (здесь"PREFA" и "PREFZ"), а остальные отсортированы в алфавитном порядке)

Я думаю, что в guava есть несколько полезных классов, которые могут выполнять эту работу (упорядочение, предикаты ...), но я пока не нашелрешение ...

Answer 1

Я предлагаю заполнить Список вашими значениями и использовать Collections.sort (...) .

Что-то вроде

Collections.sort(myList, new FunkyComparator());

используя это:

class FunkyComparator implements Comparator {

    private static Map<String,Integer> orderedExceptions =
        new HashMap<String,Integer>(){{ 
            put("PREFZ", Integer.valueOf(1));
            put("PREFA", Integer.valueOf(2));
        }};

    public int compare(Object o1, Object o2) {
        String s1 = (String) o1;
        String s2 = (String) o2;
        Integer i1 = orderedExceptions.get(s1);
        Integer i2 = orderedExceptions.get(s2);

        if (i1 != null && i2 != null) {
            return i1 - i2;
        }
        if (i1 != null) {
            return -1;
        }
        if (i2 != null) {
            return +1;
        }
        return s1.compareTo(s2);
    }
}

Answer 2

Я бы держал отдельные списки.

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

knownUnsorted.addAll(unsorted.size - 1, unknonwUnsorted);

Answer 3

Поскольку я фанат библиотеки guava, я хотел найти решение, используя ее. Я не знаю, насколько он эффективен, если вы не находите его таким же простым, как другие решения, но он здесь:

final Iterable<String> all = asList("FOO", "BAR", "PREFA", "ZOO", "PREFOO", "PREFZ");
final List<String> mustAppearFirst = asList("PREFZ", "PREFA");
final Iterable<String> sorted = 
      concat(
            Ordering.explicit(mustAppearFirst).sortedCopy(filter(all, in(mustAppearFirst))),
            Ordering.<String>natural().sortedCopy(filter(all, not(in(mustAppearFirst)))));

Answer 4

Примечание: Это не самое эффективное решение.Это просто, простое решение, которое выполняет свою работу.

Сначала я бы использовал Collections.sort(list) для сортировки списка.

Затем я удалил бы известные элементы и добавил их.на передний план.

String special = "PREFA";
if (list.remove(special)
    list.add(0, special);

Или, если у вас есть список массива этих значений, который вам необходим, вы можете сделать следующее:

String[] knownValues = {};
for (String s: knownValues) {
    if (list.remove(s))
        list.add(0, s);
}

Answer 5

Вы специально упомянули гуаву; наряду с ответом Сильвена М., вот еще один способ (больше как академическое упражнение и демонстрация гибкости гуавы, чем что-либо еще)

// List is not efficient here; for large problems, something like SkipList 
// is more suitable
private static final List<String> KNOWN_INDEXES = asList("PREFZ", "PREFA");

private static final Function<Object, Integer> POSITION_IN_KNOWN_INDEXES 
    = new Function<Object, Integer>() {
  public Integer apply(Object in) {
     int index = KNOWN_INDEXES.indexOf(in);
     return index == -1 ? null : index;
  }     
};


...


List<String> values = asList("FOO", "BAR", "PREFA", "ZOO", "PREFZ", "PREFOO");

Collections.sort(values,
  Ordering.natural().nullsLast().onResultOf(POSITION_IN_KNOWN_INDEXES).compound(Ordering.natural())
);

Таким образом, другими словами, сортировка по естественному порядку Integer, возвращенному List.indexOf(), затем разрывает связи с естественным порядком самого объекта.

Грязно, возможно, но весело.

Answer 6

Я бы также использовал Collections.sort(list), но я думаю, что я бы использовал компаратор, и в компараторе вы можете определить свои собственные правила, например,

class MyComparator implements Comparator<String> {

    public int compare(String o1, String o2) {
        // Now you can define the behaviour for your sorting.
        // For example your special cases should always come first, 
        // but if it is not a special case then just use the normal string comparison.

        if (o1.equals(SPECIAL_CASE)) {
            // Do something special
        }
        // etc.
        return o1.compareTo(o2);
    }

}

Затем отсортируйте, выполнив:

Collections.sort(list, new MyComparator());