列表排序谜题

Question

假设我有:

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

我该怎么做才能将这个未排序的列表转换成这样：

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

（首先出现已知值的列表必须首先出现（这里是“PREFA”和“PREFZ”），其余部分按字母顺序排序）

我认为在guava中有一些有用的类可以完成这项工作（Ordering，Predicates ...），但我还没有找到解决方案...

- sly7_7

---

我必须接受这种类型的练习中的解决方案吗？ - sly7_7

Answer 1

我会保持两个不同的列表。

一个用于已知值，另一个用于未知值。并分别排序，当你需要在一个列表中使用它们时，只需将它们连接起来即可。

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

- Anatoli

---

我认为这很好，但是我必须在条目中分离列表。 - sly7_7

Answer 2

我建议使用你的值填充List，并使用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);
    }
}

- Chadwick

---

不错，但是Set会消除重复项。而且，不需要虚拟的equals()方法。 - unbeli

嗯，如果我有超过两个已知值，我该如何进行转换？ - sly7_7

@unbeli 两位都说得很好。由于从SortedSet切换到List并不改变我的答案的要点，因此我已经更新了使用List的Comparator的“用法”。 - Chadwick

@Sylvain_M，只需在orderedExceptions映射中添加所需的“已知值”即可。确保使用的整数是唯一的并按您想要的顺序排序 - 映射使查找快速，但整数决定最终排序。 - Chadwick

哦，是的，所以维护起来不太难。谢谢。 - sly7_7

并且切换到列表使其与这里的其他答案（Justin'jjnguy'Nelson）相同，这并不好，因为您需要先填充列表。这个填充步骤已经可以处理分离，因此不需要使用Comparator。 - unbeli

Answer 3

注意: 这不是最有效的解决方案。它只是一个简单、直接的解决方案，能够完成工作。

我首先会使用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);
}

- jjnguy

---

list.remove() 返回的是一个布尔值，而不是你所移除的对象。但我认为这个方法可以起作用： for (final String s : asList("PREFA", "PREFZ")) { if (list.remove(s)) { list.add(0, s); } } - sly7_7

除非您将Iterable转换为列表，否则无法对其进行排序，但是这样做会使代码变得丑陋，因为在转换时就可以分离未知元素。 - unbeli

@unbeli：我同意你的观点，但是现在看来，最简单的方法就是完成工作。 - sly7_7

@unbeli：我是stackoverflow的新手，可能在常见问题解答中漏掉了些东西。 - sly7_7

@Syl Naw，你没问题。这是一个完美的问题。 - jjnguy

Answer 4

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

- sly7_7

---

不错的方法。如果你感兴趣，我在我的回答中尝试了另一种“guavaey”的方法。 - Cowan

Answer 5

我也会使用 Collections.sort(list) ，但我认为我会使用 Comparator 并在其中定义您自己的规则，例如：

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

- DaveJohnston

Answer 6

你特别提到了Guava；除了Sylvain M的答案，这里有另一种方式（更多是作为学术练习和展示Guava的灵活性而非其他任何事情）。

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

换句话说，按照List.indexOf()返回的Integer自然顺序排序，然后用对象本身的自然顺序来解决平局。

可能有些混乱，但很有趣。

- Cowan

---

嗨Cowan，我尝试了你的解决方案，但它无法编译。当我修改它以便编译（通过在排序和帮助类型推断上添加asList()），我得到了一个NPE... - sly7_7

抱歉Sylvain，在我编写时我不在编译器附近。已经修复了。由于某种原因，我认为Ordering.compound()是一个静态方法；此外，你需要使用nullsLast().onResultOf()而不是onResultOf().nullsLast()，否则它会以错误的顺序链接事物。现在对我来说可以正常工作。 - Cowan

由于我被推荐接受一个答案，因为它是我读过的最简洁的答案，所以我接受了这个答案。嗯，这是主观的，但这是我首选的答案（简洁+使用guava）。 - sly7_7