java - 在 Java 中，如何根据另一个列表对一个列表进行排序？

Question

我已经看到了与此类似的其他几个问题，但我还没有真正找到任何可以解决我的问题的问题。

我的用例是这样的：用户最初有一个项目列表（listA）。他们重新排序项目并希望保留该订单（listB），但是，由于限制，我无法在后端保留订单，因此我必须在检索后对 listA 进行排序。

所以基本上，我有 2 个 ArrayList（listA 和 listB）。一个具有列表的特定顺序（listB），另一个具有项目列表（listA）。我想根据 listB 对 listA 进行排序。

score 88 · Accepted Answer

使用 Java 8：

Collections.sort(listToSort, 
    Comparator.comparing(item -> listWithOrder.indexOf(item)));

或更好：

listToSort.sort(Comparator.comparingInt(listWithOrder::indexOf));

score 74 · Accepted Answer

Collections.sort(listB, new Comparator<Item>() {
    public int compare(Item left, Item right) {
        return Integer.compare(listA.indexOf(left), listA.indexOf(right));
    }
});

This is quite inefficient, though, and you should probably create a Map<Item, Integer> from listA to lookup the positions of the items faster.

Guava has a ready-to-use comparator for doing that: Ordering.explicit()

score 17 · Accepted Answer

假设您有一个listB列表，它定义了您想要排序的顺序listA。这只是一个示例，但它演示了由列表定义的顺序，而不是数据类型的自然顺序：

List<String> listB = Arrays.asList("Sunday", "Monday", "Tuesday", "Wednesday",
    "Thursday", "Friday", "Saturday");

现在，假设listA需要根据此排序进行排序。它是一个List<Item>，并且Item有一个public String getWeekday()方法。

创建一个Map<String, Integer>将所有内容的值映射listB到可以轻松排序的东西，例如索引，即"Sunday"=> 0，...，"Saturday"=> 6。这将提供快速简便的查找。

Map<String, Integer> weekdayOrder = new HashMap<String, Integer>();
for (int i = 0; i < listB.size(); i++)
{
    String weekday = listB.get(i);
    weekdayOrder.put(weekday, i);
}

然后，您可以创建Comparator<Item>使用Map来创建订单的自定义：

public class ItemWeekdayComparator implements Comparator<Item>
{
    private Map<String, Integer> sortOrder;

    public ItemWeekdayComparator(Map<String, Integer> sortOrder)
    {
        this.sortOrder = sortOrder;
    }

    @Override
    public int compare(Item i1, Item i2)
    {
        Integer weekdayPos1 = sortOrder.get(i1.getWeekday());
        if (weekdayPos1 == null)
        {
            throw new IllegalArgumentException("Bad weekday encountered: " +
               i1.getWeekday());
        }
        Integer weekdayPos2 = sortOrder.get(i2.getWeekday());
        if (weekdayPos2 == null)
        {
            throw new IllegalArgumentException("Bad weekday encountered: " +
               i2.getWeekday());
        }
        return weekdayPos1.compareTo(weekdayPos2);
    }
}

listA然后你可以使用你的自定义排序Comparator。

Collections.sort(listA, new ItemWeekdayComparator(weekdayOrder));

score 13 · Accepted Answer

JB Nizet 答案的速度改进（来自他自己提出的建议）。使用这种方法：

在我的单元测试中，对 1000 个项目列表进行 100 次排序可以将速度提高 10 倍。
在我的单元测试中，对 10000 个项目列表进行 100 次排序可将速度提高 140 倍（整个批次为 265 毫秒而不是 37 秒）。

当两个列表不相同时，此方法也将起作用：

/**
 * Sorts list objectsToOrder based on the order of orderedObjects.
 * 
 * Make sure these objects have good equals() and hashCode() methods or
 * that they reference the same objects.
 */
public static void sortList(List<?> objectsToOrder, List<?> orderedObjects) {

    HashMap<Object, Integer> indexMap = new HashMap<>();
    int index = 0;
    for (Object object : orderedObjects) {
        indexMap.put(object, index);
        index++;
    }

    Collections.sort(objectsToOrder, new Comparator<Object>() {

        public int compare(Object left, Object right) {

            Integer leftIndex = indexMap.get(left);
            Integer rightIndex = indexMap.get(right);
            if (leftIndex == null) {
                return -1;
            }
            if (rightIndex == null) {
                return 1;
            }

            return Integer.compare(leftIndex, rightIndex);
        }
    });
}

score 7 · Accepted Answer

这是一个将时间复杂度增加的解决方案2n，但可以完成您想要的。它也不关心R您要排序的 List 是否包含 Comparable 元素，只要L您用来对其进行排序的另一个 List 是一致的 Comparable 即可。

public class HeavyPair<L extends Comparable<L>, R> implements Comparable<HeavyPair<L, ?>> {
    public final L left;
    public final R right;

    public HeavyPair(L left, R right) {
        this.left = left;
        this.right = right;
    }

    public compareTo(HeavyPair<L, ?> o) {
        return this.left.compareTo(o.left);
    }

    public static <L extends Comparable<L>, R> List<R> sort(List<L> weights, List<R> toSort) {
        assert(weights.size() == toSort.size());
        List<R> output = new ArrayList<>(toSort.size());
        List<HeavyPair<L, R>> workHorse = new ArrayList<>(toSort.size());
        for(int i = 0; i < toSort.size(); i++) {
            workHorse.add(new HeavyPair(weights.get(i), toSort.get(i)))
        }
        Collections.sort(workHorse);
        for(int i = 0; i < workHorse.size(); i++) {
            output.add(workHorse.get(i).right);
        }
        return output;
    }
}

不过，请原谅我在编写此代码时使用的任何糟糕做法。我很着急。

打电话HeavyPair.sort(listB, listA);

编辑：修复了这一行return this.left.compareTo(o.left);。现在它确实有效。

score 7 · Accepted Answer

问题：根据另一个列表中存在的字段的所有可能值之一对 Pojo 列表进行排序。

看看这个解决方案，可能这就是你想要实现的：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Test {

  public static void main(String[] args) {
    List<Employee> listToSort = new ArrayList<>();
    listToSort.add(new Employee("a", "age11"));
    listToSort.add(new Employee("c", "age33"));
    listToSort.add(new Employee("b", "age22"));
    listToSort.add(new Employee("a", "age111"));
    listToSort.add(new Employee("c", "age3"));
    listToSort.add(new Employee("b", "age2"));
    listToSort.add(new Employee("a", "age1"));

    List<String> listWithOrder = new ArrayList<>();
    listWithOrder.add("a");
    listWithOrder.add("b");
    listWithOrder.add("c");

    Collections.sort(listToSort, Comparator.comparing(item -> 
    listWithOrder.indexOf(item.getName())));
    System.out.println(listToSort);
  }

}


class Employee {
  String name;
  String age;

  public Employee(String name, String age) {
    super();
    this.name = name;
    this.age = age;
  }

  public String getName() {
    return name;
  }

  public String getAge() {
    return age;
  }

  @Override
  public String toString() {
    return "[name=" + name + ", age=" + age + "]";
  }
}

输出 [[name=a，age=age11]，[name=a，age=age111]，[name=a，age=age1]，[name=b，age=age22]，[name=b，age=age2 ], [姓名=c, 年龄=33], [姓名=c, 年龄=33]]

score 2 · Accepted Answer

Here is an example of how to sort a list and then make the changes in another list according to the changes exactly made to first array list. This trick will never fails and ensures the mapping between the items in list. The size of both list must be same to use this trick.

    ArrayList<String> listA = new ArrayList<String>();
    ArrayList<String> listB = new ArrayList<String>();
    int j = 0;
    // list of returns of the compare method which will be used to manipulate
    // the another comparator according to the sorting of previous listA
    ArrayList<Integer> sortingMethodReturns = new ArrayList<Integer>();

    public void addItemstoLists() {
        listA.add("Value of Z");
        listA.add("Value of C");
        listA.add("Value of F");
        listA.add("Value of A");
        listA.add("Value of Y");

        listB.add("this is the value of Z");
        listB.add("this is the value off C");
        listB.add("this is the value off F");
        listB.add("this is the value off A");
        listB.add("this is the value off Y");

        Collections.sort(listA, new Comparator<String>() {

            @Override
            public int compare(String lhs, String rhs) {
                // TODO Auto-generated method stub
                int returning = lhs.compareTo(rhs);
                sortingMethodReturns.add(returning);
                return returning;
            }

        });
        // now sort the list B according to the changes made with the order of
        // items in listA
        Collections.sort(listB, new Comparator<String>() {

            @Override
            public int compare(String lhs, String rhs) {
                // TODO Auto-generated method stub

                // comparator method will sort the second list also according to
                // the changes made with list a
                int returning = sortingMethodReturns.get(j);
                j++;
                return returning;
            }

        });

    }

score 2 · Accepted Answer

import java.util.Comparator;
import java.util.List;

public class ListComparator implements Comparator<String> {

    private final List<String> orderedList;
    private boolean appendFirst;

    public ListComparator(List<String> orderedList, boolean appendFirst) {
        this.orderedList = orderedList;
        this.appendFirst = appendFirst;
    }

    @Override
    public int compare(String o1, String o2) {
        if (orderedList.contains(o1) && orderedList.contains(o2))
            return orderedList.indexOf(o1) - orderedList.indexOf(o2);
        else if (orderedList.contains(o1))
            return (appendFirst) ? 1 : -1;
        else if (orderedList.contains(o2))
            return (appendFirst) ? -1 : 1;
        return 0;
    }
}

您可以使用此通用比较器根据另一个列表对列表进行排序。例如，当 appendFirst 为 false 时，下面将是输出。

有序列表：[a, b]

无序列表：[d, a, b, c, e]

输出：[a, b, d, c, e]

score 1 · Accepted Answer

不完全清楚你想要什么，但如果是这种情况： A:[c,b,a] B:[2,1,0]

您想同时加载它们，然后生成： C:[a,b,c]

那么也许这个？

List c = new ArrayList(b.size());
for(int i=0;i<b.size();i++) {
  c.set(b.get(i),a.get(i));
}

这需要一个额外的副本，但我认为它的效率要低得多，而且各种不清楚：

for(int i=0;i<b.size();i++){
    int from = b.get(i);
    if(from == i) continue;
    T tmp = a.get(i);
    a.set(i,a.get(from));
    a.set(from,tmp);
    b.set(b.lastIndexOf(i),from); 
}

注意我也没有测试，也许有一个标志被翻转了。

score 1 · Accepted Answer

One way of doing this is looping through listB and adding the items to a temporary list if listA contains them:

List<?> tempList = new ArrayList<?>();
for(Object o : listB) {
    if(listA.contains(o)) {
        tempList.add(o);
    }
}
listA.removeAll(listB);
tempList.addAll(listA);
return tempList;

score 1 · Accepted Answer

另一种可能取决于您的设置的解决方案不是将实例存储在 listB 中，而是从 listA 中存储索引。这可以通过将 listA 包装在自定义排序列表中来完成，如下所示：

public static class SortedDependingList<E> extends AbstractList<E> implements List<E>{
    private final List<E> dependingList;
    private final List<Integer> indices;

    public SortedDependingList(List<E> dependingList) {
        super();
        this.dependingList = dependingList;
        indices = new ArrayList<>();
    }

    @Override
    public boolean add(E e) {
        int index = dependingList.indexOf(e);
        if (index != -1) {
            return addSorted(index);
        }
        return false;
    }

    /**
     * Adds to this list the element of the depending list at the given
     * original index.
     * @param index The index of the element to add.
     * 
     */
    public boolean addByIndex(int index){
        if (index < 0 || index >= this.dependingList.size()) {
            throw new IllegalArgumentException();
        }
        return addSorted(index);
    }

    /**
     * Returns true if this list contains the element at the
     * index of the depending list.
     */
    public boolean containsIndex(int index){
        int i = Collections.binarySearch(indices, index);
        return i >= 0;
    }

    private boolean addSorted(int index){
        int insertIndex = Collections.binarySearch(indices, index);
        if (insertIndex < 0){
            insertIndex = -insertIndex-1;
            this.indices.add(insertIndex, index);
            return true;
        }
        return false;
    }

    @Override
    public E get(int index) {
        return dependingList.get(indices.get(index));
    }

    @Override
    public int size() {
        return indices.size();
    }
}

然后您可以按如下方式使用此自定义列表：

public static void main(String[] args) {
    class SomeClass{
        int index;
        public SomeClass(int index) {
            super();
            this.index = index;
        }
        @Override
        public String toString() {
            return ""+index;
        }
    }

    List<SomeClass> listA = new ArrayList<>();
    for (int i = 0; i < 100; i++) {
        listA.add(new SomeClass(i));
    }
    SortedDependingList<SomeClass> listB = new SortedDependingList<>(listA);
    Random rand = new Random();

    // add elements by index:
    for (int i = 0; i < 5; i++) {
        int index = rand.nextInt(listA.size());
        listB.addByIndex(index);
    }

    System.out.println(listB);

    // add elements by identity:
    for (int i = 0; i < 5; i++) {
        int index = rand.nextInt(listA.size());
        SomeClass o = listA.get(index);
        listB.add(o);
    }
    System.out.println(listB);      
}

当然，这个自定义列表只有在原始列表中的元素没有改变的情况下才有效。如果可以更改，您将需要以某种方式侦听对原始列表的更改并更新自定义列表中的索引。

另请注意，SortedDependingList 目前不允许第二次添加 listA 中的元素 - 在这方面，它实际上就像 listA 中的一组元素一样，因为这通常是您在这样的设置中想要的。

向 SortedDependingList 添加内容的首选方法是已经知道元素的索引并通过调用 sortedList.addByIndex(index); 来添加它。

score 1 · Accepted Answer

试试这个java 8：

listB.sort((left, right) -> Integer.compare(list.indexOf(left), list.indexOf(right)));

或者

listB.sort(Comparator.comparingInt(item -> list.indexOf(item)));

score 1 · Accepted Answer

List<String> listA;
Comparator<B> comparator = Comparator.comparing(e -> listA.indexOf(e.getValue()));
//call your comparator inside your list to be sorted
listB.stream().sorted(comparator)..

score 0 · Accepted Answer

Like Tim Herold wrote, if the object references should be the same, you can just copy listB to listA, either:

listA = new ArrayList(listB);

Or this if you don't want to change the List that listA refers to:

listA.clear();
listA.addAll(listB);

If the references are not the same but there is some equivalence relationship between objects in listA and listB, you could sort listA using a custom Comparator that finds the object in listB and uses its index in listB as the sort key. The naive implementation that brute force searches listB would not be the best performance-wise, but would be functionally sufficient.

score 0 · Accepted Answer

IMO，你需要坚持别的东西。可能不是完整的列表 B，而是某些东西。可能只是用户更改的项目的索引。

score 0 · Accepted Answer

如果对象引用应该相同，则可以将 listA 初始化为新的。

listA = new ArrayList(listB)

score 0 · Accepted Answer

尝试这个。下面的代码对于 listA 是一个列表的场景是通用的，Objects因为您没有指示特定类型。

Object[] orderedArray = new Object[listA.size()];

for(int index = 0; index < listB.size(); index ++){
    int position = listB.get(index); //this may have to be cast as an int
    orderedArray[position] = listA.get(index);
}
//if you receive UnsupportedOperationException when running listA.clear()
//you should replace the line with listA = new List<Object>() 
//using your actual implementation of the List interface
listA.clear(); 
listA.addAll(orderedArray);

score 0 · Accepted Answer

为了避免非常低效的查找，您应该索引项目，listB然后listA根据它进行排序。

Map<Item, Integer> index = IntStream.range(0, listB.size()).boxed()
  .collect(Collectors.toMap(listB::get, x -> x));

listA.sort((e1, e2) -> Integer.compare(index.get(c1), index.get(c2));

score 0 · Accepted Answer

如果保证两个列表包含相同的元素，只是顺序不同，则可以使用List<T> listA = new ArrayList<>(listB)，这将是O(n)时间复杂度。否则，我在这里使用看到很多答案Collections.sort()，但是有一种替代方法可以保证O(2n)运行时，理论上它应该比sort的最坏时间复杂度更快，但以存储O(nlog(n))为代价2n

Set<T> validItems = new HashSet<>(listB);
listA.clear();
listB.forEach(item -> {
  if(validItems.contains(item)) {
    listA.add(item);
  }
});

score 0 · Accepted Answer

刚遇到同样的问题。
我有一个有序键的列表，我需要根据键的顺序对列表中的对象进行排序。
我的列表足够长，使得时间复杂度为 N^2 的解决方案无法使用。
我的解决方案：

<K, T> List<T> sortByOrder(List<K> orderedKeys, List<T> objectsToOrder, Function<T, K> keyExtractor) {
    AtomicInteger ind = new AtomicInteger(0);
    Map<K, Integer> keyToIndex = orderedKeys.stream().collect(Collectors.toMap(k -> k, k -> ind.getAndIncrement(), (oldK, newK) -> oldK));
    SortedMap<Integer, T> indexToObj = new TreeMap<>();
    objectsToOrder.forEach(obj -> indexToObj.put(keyToIndex.get(keyExtractor.apply(obj)), obj));
    return new ArrayList<>(indexToObj.values());
}

时间复杂度为 O(N * Log(N))。
该解决方案假定要排序的列表中的所有对象都具有不同的键。如果不是，那么只需替换SortedMap<Integer, T> indexToObj为SortedMap<Integer, List<T>> indexToObjList.

score 0 · Accepted Answer

所以对我来说，要求是originalList用orderedList. originalList总是包含来自的所有元素orderedList，但反之则不然。没有新元素。

fun <T> List<T>.sort(orderedList: List<T>): List<T> {
    return if (size == orderedList.size) {
        orderedList
    } else {
        var keepIndexCount = 0
        mapIndexed { index, item ->
            if (orderedList.contains(item)) {
                orderedList[index - keepIndexCount]
            } else {
                keepIndexCount++
                item
            }
    }
}}

PS我的情况是我有列表，用户可以通过拖放进行排序，但有些项目可能会被过滤掉，所以我们保留隐藏项目的位置。

score -2 · Accepted Answer

In Java there are set of classes which can be useful to sort lists or arrays. Most of the following examples will use lists but the same concept can be applied for arrays. A example will show this.

We can use this by creating a list of Integers and sort these using the Collections.sort(). The Collections (Java Doc) class (part of the Java Collection Framework) provides a list of static methods which we can use when working with collections such as list, set and the like. So in a nutshell, we can sort a list by simply calling: java.util.Collections.sort(the list) as shown in the following example:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class example {
  public static void main(String[] args) {
    List<Integer> ints = new ArrayList<Integer>();
    ints.add(4);
    ints.add(3);
    ints.add(7);
    ints.add(5);
    Collections.sort(ints);
    System.out.println(ints);
  }
}

The above class creates a list of four integers and, using the collection sort method, sorts this list (in one line of code) without us having to worry about the sorting algorithm.

java - 在 Java 中，如何根据另一个列表对一个列表进行排序？

22 回答 22

Related

Reference