Java 自定义排序顺序 Round Robin-ish 排序

Question

我是 Java 开发人员，但我正在为我需要做的特定类型的排序寻找一个好的算法。

基本上，我将获得一些从查询返回的数据（最多几千行）。我只关心基于单列的排序。具有讽刺意味的是，该列可能已经排序，但不是我需要的方式。

就是这样：

我得到了一个用户 ID 列表，我需要对它们进行排序，使其贯穿整个列表并重新开始。一个简单的例子比解释更容易：

假设数据是这样的：

A A A B B C D D

对我而言，有效的排序顺序是这样的：

A B C D A B D A

基本上，我需要每个用户在回到他们之前“轮流”。用户的数量可能是奇数，因此任何额外的用户都可以放在最后。

同样，我在 Java 中执行此操作，但此时并没有锁定到特定的数据结构，等等。

[附加信息：如果有帮助，特别是我正在做的是为负载测试生成数据并希望将同一用户多次登录应用程序的次数最小化，因此我希望我的测试在返回之前循环遍历所有可用的应用程序用户到列表的开头。不过，这些数据是真实数据，我不能保证每个用户都会有相同数量的活动。]

谢谢！汤姆

Answer 1

1. 通过您想要的任何分组函数将值分组到 LinkedList 类型结构中。

2. 通过轮询每个组将它们添加到最终结果集合中。

前任）

鉴于：

public class MyObject {

    private String name;

    public MyObject(String name) {
        super();
        this.name = name;
    }

    public String getName() {
        return name;
    }

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

数据集：

List<MyObject> objects = new ArrayList<>();


        objects.addAll( Arrays.asList(
            new MyObject("A"),
            new MyObject("C"),
            new MyObject("A"),
            new MyObject("B"),
            new MyObject("B"),
            new MyObject("B"),
            new MyObject("A"),
            new MyObject("A"),
            new MyObject("C"),
            new MyObject("C"),
            new MyObject("A"),
            new MyObject("C")
        ));

和功能：

public static Queue<MyObject> robin(List<MyObject> objects) {

        if(objects.size() == 0) return new LinkedList<>();

        // Group into queues using the getName method
        Map<String, Queue<MyObject>> map = objects.stream()
                .collect(Collectors.groupingBy(MyObject::getName, Collectors.toCollection(LinkedList::new)));

        boolean remaining = true;
        Deque<MyObject> roundRobin = new LinkedList<MyObject>();

        Set<String> keySet = map.keySet();

        // Round robin structure to collect them into a single collection
        while(remaining) {
            remaining = false;
            for(String key : keySet) {
                MyObject obj = map.get(key).poll();
                if(obj == null) continue;
                roundRobin.add(obj);
                remaining = true;
            }
        }

        // Return result
        return roundRobin;
    }

结果排序：

A B C A B C A B C A C A