Java集合的排序和分组

Question

我有一个对象，它有一个名称和一个分数。我想对这样的对象集合进行排序，使它们按名称分组，并按每个组中的最大分数进行排序（在组内也按降序得分排序）。

让我演示一下我的意图。假设我有这些对象(名称，分数):

(a, 3)
(a, 9)
(b, 7)
(b, 10)
(c, 8)
(c, 3)

然后我希望它们按照以下方式排序：

(b, 10)
(b, 7)
(a, 9)
(a, 3)
(c, 8)
(c, 3)

使用Comparator实现这个功能是否可行？ 我无法想出来，所以非常感谢任何提示。

- pmeidl

---

据我理解，您想要的是类似于 GROUP BY name ORDER BY MAX(score), score DESC 的等效排序，而不是 ORDER BY name, score？ - Christoffer Hammarström

@user639755：你能否更具体地说明你的意图是什么？就像 Christoffer 所写的那样。 - Marcus

@Marcus：他提供了带有预期输出的示例输入，编写assertEquals很简单。 - Christoffer Hammarström

Answer 1

不能使用单一的Comparator进行排序。

你需要：

1. 按名称对数据进行分组
2. 对每个分组内的元素按照得分从高到低排序
3. 然后需要将分组展平并转换为列表

利用Java 8

编辑：自从我写下这个答案之后，Java 8已经发布了，这大大简化了问题：

import java.util.*;
import static java.util.Comparator.*;
import static java.util.stream.Collectors.*;

---

List<Record> result = records.stream()
    .sorted(comparingInt(Record::getScore).reversed())
    .collect(groupingBy(Record::getName, LinkedHashMap::new, toList()))
    .values().stream()
    .flatMap(Collection::stream)
    .collect(toList());

首先我们按照分数降序排序，然后使用 LinkedHashMap 进行分组，这样可以保留键的插入顺序，因此拥有更高分数的键将排在前面。

如果组比较小，则先排序是可以的，因此不同组之间对象之间冗余的比较不会太耗费时间。

此外，使用这种方法还可以保留重复项。

---

或者，如果您不介意保留重复项，可以：

Comparator<Record> highestScoreFirst = comparingInt(Record::getScore).reversed();

List<Record> result = records.stream()
        .collect(groupingBy(Record::getName,
                toCollection(() -> new TreeSet<>(highestScoreFirst))))
        .values().stream()
        .sorted(comparing(SortedSet::first, highestScoreFirst))
        .flatMap(Collection::stream)
        .collect(toList());

如果记录被分组到已排序的TreeSet中，而不是将值作为流的第一个操作进行排序，然后按其第一个最高值对集合进行排序。

如果组很大，分组再排序是适当的，以减少冗余比较。

---

实现Comparable：

您可以通过让记录实现Comparable来缩短代码。

public class Record implements Comparable<Record> {
    @Override
    public int compareTo(Record other) {
        // Highest first
        return -Integer.compare(getScore(), other.getScore());

        /* Or equivalently:
           return Integer.compare(other.getScore(), getScore());
        */
    }
    ...
}

---

List<Record> result = records.stream()
    .collect(groupingBy(Record::getName, toCollection(TreeSet::new)))
    .values().stream()
    .sorted(comparing(SortedSet::first))
    .flatMap(Collection::stream)
    .collect(toList());

---

Java 8之前

编辑：下面是一个演示一种方法的非常基础的单元测试。我没有像我希望的那样对其进行过多的清理。

在Java中处理这样的事情很麻烦，而我通常会使用Google Guava来完成。

import org.junit.Test;

import java.util.*;

import static java.util.Arrays.asList;
import static org.junit.Assert.assertEquals;

public class GroupSortTest {

    @Test
    public void testGroupSort() {
        List<Record> records = asList(
                new Record("a", 3),
                new Record("a", 9),
                new Record("b", 7),
                new Record("b", 10),
                new Record("c", 8),
                new Record("c", 3));

        List<SortedMap<Integer, Record>> recordsGroupedByName = groupRecordsByNameAndSortedByScoreDescending(records);
        Collections.sort(recordsGroupedByName, byHighestScoreInGroupDescending());
        List<Record> result = flattenGroups(recordsGroupedByName);

        List<Record> expected = asList(
                new Record("b", 10),
                new Record("b", 7),
                new Record("a", 9),
                new Record("a", 3),
                new Record("c", 8),
                new Record("c", 3));

        assertEquals(expected, result);
    }

    private List<Record> flattenGroups(List<SortedMap<Integer, Record>> recordGroups) {
        List<Record> result = new ArrayList<Record>();
        for (SortedMap<Integer, Record> group : recordGroups) {
            result.addAll(group.values());
        }
        return result;
    }

    private List<SortedMap<Integer, Record>> groupRecordsByNameAndSortedByScoreDescending(List<Record> records) {
        Map<String, SortedMap<Integer, Record>> groupsByName = new HashMap<String, SortedMap<Integer, Record>>();
        for (Record record : records) {
            SortedMap<Integer, Record> group = groupsByName.get(record.getName());
            if (null == group) {
                group = new TreeMap<Integer, Record>(descending());
                groupsByName.put(record.getName(), group);
            }
            group.put(record.getScore(), record);
        }
        return new ArrayList<SortedMap<Integer, Record>>(groupsByName.values());
    }

    private DescendingSortComparator descending() {
        return new DescendingSortComparator();
    }

    private ByFirstKeyDescending byHighestScoreInGroupDescending() {
        return new ByFirstKeyDescending();
    }

    private static class ByFirstKeyDescending implements Comparator<SortedMap<Integer, Record>> {
        public int compare(SortedMap<Integer, Record> o1, SortedMap<Integer, Record> o2) {
            return o2.firstKey().compareTo(o1.firstKey());
        }
    }

    private static class DescendingSortComparator implements Comparator<Comparable> {
        public int compare(Comparable o1, Comparable o2) {
            return o2.compareTo(o1);
        }
    }
}

- Christoffer Hammarström

---

@Amir：除此之外，其他答案实际上都没有读懂问题，该问题要求按每个姓名的最高分数对姓名进行排序。其他答案只告诉您如何按得分和姓名对单个记录进行排序，而不是按姓名分组，这是不同的事情。 - Christoffer Hammarström

@Amir: 这不是问题的关键。问题要求首先将所有b:s排序，因为其中一个b:s具有最高的总分数，然后将所有a:s排序，因为其中一个a:s具有第二高的总分数，依此类推。如果您熟悉SQL，他想要的是 GROUP BY name ORDER BY MAX(score), score DESC，而不是 ORDER BY name, score（类似于这样排序）。 - Christoffer Hammarström

未找到符号 comparingInt。对于方法 groupingBy() 和 toList()，必须指定 Collectors 类。 - Alex78191

@Alex78191：谢谢，还需要import java.util.*。我加上了导入。 - Christoffer Hammarström

@Alex78191：哈哈，再次感谢，我实际上还没有按保存。 :) - Christoffer Hammarström

Answer 2

遍历集合，并将对象放入一个Map<String, SortedSet<YourObject>>中，按名称进行分组，其中SortedSet是一个TreeSet，具有自定义比较器，按得分进行比较。

然后遍历地图的values()集合，并将组放入一个SortedSet<SortedSet<YourObject>>中，使用第二个自定义比较器，根据它们最大元素的大小比较SortedSets。实际上，你可以简单地使用addAll()而不是foreach。

这是代码：

public class SortThings {

    static class Thing {
        public final String name;
        public final int score;
        public Thing(String name, int score) {
            this.name = name;
            this.score = score;
        }
        @Override
        public String toString() {
            return "(" + name + ", " + score + ")";
        }
    }

    public static void main(String[] args) {
        Collection<Thing> things = Arrays.asList(
            new Thing("a", 3),
            new Thing("a", 9),
            new Thing("b", 7),
            new Thing("b", 10),
            new Thing("c", 8),
            new Thing("c", 3)
        );

        SortedSet<SortedSet<Thing>> sortedGroups = sortThings(things);

        System.out.println(sortedGroups);
    }

    private static SortedSet<SortedSet<Thing>> sortThings(Collection<Thing> things) {
        final Comparator<Thing> compareThings = new Comparator<Thing>() {
            public int compare(Thing a, Thing b) {
                Integer aScore = a.score;
                Integer bScore = b.score;
                return aScore.compareTo(bScore);
            }
        };

        // first pass
        Map<String, SortedSet<Thing>> groups = new HashMap<String, SortedSet<Thing>>();
        for (Thing obj: things) {
            SortedSet<Thing> group = groups.get(obj.name);
            if (group == null) {
                group = new TreeSet<Thing>(compareThings);
                groups.put(obj.name, group);
            }
            group.add(obj);
        }

        // second pass
        SortedSet<SortedSet<Thing>> sortedGroups = new TreeSet<SortedSet<Thing>>(new Comparator<SortedSet<Thing>>() {
            public int compare(SortedSet<Thing> a, SortedSet<Thing> b) {
                return compareThings.compare(a.last(), b.last());
            }
        });
        sortedGroups.addAll(groups.values());
        return sortedGroups;
    }

}

请注意，输出是按照从小到大的顺序排列的。这是Java集合的自然顺序；如果需要按照其他方式排序，修改代码将非常简单。

- Tom Anderson

---

要处理重复项，可以使用SortedMap或按照分数和标识符对每个集合进行排序。 - Christoffer Hammarström

据我所知，我的代码通过去重处理来处理重复的“Things”。您能详细说明一下您的意思吗，Christoffer Hammarström先生？ - Tom Anderson

去重并不是真正的处理它们。如果我输入两个相等但不完全相同的Thing，我希望在结果中得到两个相等但不完全相同的Thing。你刚刚让我意识到我自己也有同样的错误！天啊！ :) - Christoffer Hammarström

@Christoffer：我们不确定重复项的正确处理方式。如果 OP 的目标只是为了按顺序获取组，去重是可以的。如果不是，那么是的，这段代码是错误的；修复方法是更改 compareThings 以某种方式打破关系（我认为必须是任意的，例如通过哈希码）。我仍然不明白 SortedMap 如何有所帮助。 - Tom Anderson

你在两个问题上都是正确的，一个 SortedMap 并没有帮助。那只是我一时的错误思考。此外，你是对的，我们不知道 OP 是否关心重复项。我只是认为通常更有可能需要一个非破坏性的算法，并且由于这是一个稍微更难解决的问题，如果保留了重复项，解决方案将更加完整。 - Christoffer Hammarström

Answer 3

public class ScoreComparator implements Comparator<Item>
{

  public int compare(Item a, Item b){

    if (a.name.equals(b.name){
      return a.score.compareTo(b.score);
    }

    return a.name.compareTo(b.Name);    

  }

}

- Marcus

---

我进行了点踩，因为这种排序方式是按名称和分数排序，而不是按名称分组并在组内按最高分数排序。 - Christoffer Hammarström

Answer 4

是的，使用Comparator。

在比较中首选name，然后是score。它将与排序后的score一起分组。

    List<Score> scores = new ArrayList<Score>();
    scores.add(new Score("a", 58));
    scores.add(new Score("a", 10));
    scores.add(new Score("b", 165));
    scores.add(new Score("a", 1));
    scores.add(new Score("b", 1658));
    scores.add(new Score("c", 1));
    scores.add(new Score("c", 10));
    scores.add(new Score("c", 0));

    Collections.sort(scores, new Comparator<Score>() {

        public int compare(Score o1, Score o2) {
            if (o1.getName().compareTo(o2.getName()) == 0) {
                return o2.getScore() - o1.getScore();
            } else {
                return o1.getName().compareTo(o2.getName());
            }
        }
    });
    System.out.println(scores);

更新

正如Chris所指出的那样。

import java.util.*;

/**
 *
 * @author Jigar
 */
class Score {

    private String name;
    private List<Integer> scores;

    public Score() {
    }

    public Score(String name, List<Integer> scores) {
        this.name = name;
        this.scores = scores;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public List<Integer> getScores() {
        return scores;
    }

    public void setScores(List<Integer> scores) {
        this.scores = scores;
    }

    @Override
    public String toString() {
        return name + " , " + scores + "\n";
    }
}

public class ScoreDemo { 

    public static void main(String[] args) {
        List<Score> scores = new ArrayList<Score>();


        List<Integer> lstA = new ArrayList<Integer>();
        lstA.add(3);
        lstA.add(9);
        lstA.add(7);
        Collections.sort(lstA);
        Collections.reverse(lstA);

        List<Integer> lstB = new ArrayList<Integer>();
        lstB.add(10);
        lstB.add(8);
        lstB.add(3);
        Collections.sort(lstB);
        Collections.reverse(lstB);

        List<Integer> lstC = new ArrayList<Integer>();
        lstC.add(8);
        lstC.add(3);
        Collections.sort(lstC);
        Collections.reverse(lstC);


        scores.add(new Score("a", lstA));
        scores.add(new Score("b", lstB));
        scores.add(new Score("c", lstC));





        Collections.sort(scores, new Comparator<Score>() {

            public int compare(Score o1, Score o2) {
                return o2.getScores().get(0).compareTo(o1.getScores().get(0));
            }
        });
        System.out.println(scores);

    }
}

• 这里有一个能用的ideone演示

• 更新：这里有一个能用的ideone演示

- jmj

---

有人在四处乱踩。我的另一篇帖子也遭到了这种情况。很烦人。不过，对于好的答案我会点赞。我会使用equals()函数。 - Amir Raminfar

谁对此进行了负面评价：为什么？为什么你没有对Adam Batkin的答案进行同样的评价，因为它与此基本相同？ - Tom Anderson

@Tom 不用担心，他们也得到了我的。 - Adam Batkin

我投反对票，因为这种排序方式是按名称和分数排序，并不是按名称分组然后在组内按最高分数排序。 - Christoffer Hammarström

@Adam，重点不在于这项活动现在非常频繁地进行，而且它完全是不合逻辑的。 - jmj

Answer 5

我认为你可以做到这一点。首先检查组是否相等。如果是，则比较分数。否则返回你想要更靠前的组。让我编写代码。

    class Item{
      String name;
      int score;
    }

   new Comparator<Item>(){

       @Override
       public int compare(Item o1, Item o2) {
            if (o1.name.equals(o2.name)) {
                return o1.score > o2.score ? 1 : -1; // might have to flip this. I didn't test
            }else {
                return o1.name.compareTo(o2.name);
            }
       }
    };

- Amir Raminfar

---

我给你点了个踩，因为这个排序是按照姓名和分数来进行的，而不是按照姓名分组并在每个组内按最高分数排序。 - Christoffer Hammarström

我必须同意你的观点。起初我的表述不够清晰。但是如果他想让最高分数排在前面，那么确实是不可能的。对于造成的困扰，我感到非常抱歉。 - Amir Raminfar