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

小开

如果对象引用应该相同，则可以初始化 listAnew。

listA = new ArrayList(listB)

小开

这样做的一种方法是循环遍历 listB，如果 listA 包含这些项，则将它们添加到临时列表中:

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

小开

就像 Tim Herold 写的，如果对象引用应该是相同的，你可以直接把 listB 复制到 listA，或者:

listA = new ArrayList(listB);

或者，如果您不想更改 listA 引用的 List，可以这样做:

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

如果引用不相同，但 listA 和 listB 中的对象之间存在某种等价关系，那么可以使用自定义 Comparator对 listA 进行排序，该 Comparator在 listB 中查找对象，并使用 listB 中的索引作为排序键。粗暴强制搜索 listB 的幼稚实现在性能方面并不是最好的，但在功能上已经足够了。

小开

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

但是这样做效率很低，您可能应该从 listA 创建一个 Map<Item, Integer>来更快地查找项的位置。

番石榴有一个现成的比较器: Ordering.explicit()

小开

不完全清楚你想要什么，但如果是这种情况: 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);
}

注意，我也没有测试，可能得到了一个标志翻转。

小开

假设您有一个 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);
}

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

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

然后可以使用自定义 Comparator对 listA进行排序。

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

小开

另一个可以根据您的设置工作的解决方案是不在 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)来添加该元素;

小开

在 Java 中，有一组类可以用来对列表或数组进行排序。下面的大多数示例将使用列表，但同样的概念也可以应用于数组。一个例子可以说明这一点。

我们可以通过创建一个整数列表来使用它，并使用 Collections.sort ()对它们进行排序。Colltions (Java Doc)类(Java Collection Framework 的一部分)提供了一个静态方法列表，我们可以在处理 list、 set 等集合时使用这些方法。所以简而言之，我们可以通过简单地调用: java.util 对列表进行排序。Sort (列表) ，如下面的示例所示:

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

上面的类创建了一个包含4个整数的列表，并使用集合排序方法对这个列表(在一行代码中)进行排序，而不用担心排序算法。

小开

我的意思是，你需要坚持一些其他的东西。可能不是完整的列表 B，但 什么东西。可能只是用户更改的项的索引。

小开

试试这个。下面的代码对于 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);

小开

这里有一个解决方案，它通过 2n增加了时间复杂性，但是完成了您想要的任务。它也不关心您想要排序的 List R是否包含 Compaable 元素，只要您用来对它们进行排序的 List L是统一 Compaable 元素。

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);。现在它实际上工作。

小开

下面是一个示例，演示如何对一个列表进行排序，然后根据对第一个数组列表所做的更改在另一个列表中进行更改。这个技巧将永远不会失败，并确保列表中的项目之间的映射。要使用这个技巧，两个列表的大小必须相同。

    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;
}


});


}

小开

使用 Java8:

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

或者更好:

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

小开

对 JB · 尼泽特的回答(从他自己提出的建议中)的速度改进。使用这种方法:

对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);
}
});
}

小开

试试这个 java 8:

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

或者

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

小开

只是遇到了同样的问题。
我有一个有序键的列表，我需要根据键的顺序对列表中的对象进行排序。
我的列表足够长，使时间复杂度为 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。

小开

为了避免非常低效的查找，您应该索引 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));

小开

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;
}
}

可以使用此通用比较器根据其他列表对列表进行排序。例如，如果下面的附加值为 false，则输出为。

有序列表: [ a，b ]

无序列表: [ d，a，b，c，e ]

产出: [ a，b，d，c，e ]

小开

问题: 根据另一个列表中某个字段的所有可能值对波霍列表进行排序。

看看这个解决方案，也许这就是你想要达到的效果:

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] ，[ name = c，age = age33] ，[ name = c，age = age3]

小开

如果两个列表保证包含相同的元素，只是顺序不同，您可以使用 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);
}
});

小开

所以对我来说，需要用 orderedList对 originalList进行排序。originalList总是包含来自 orderedList的所有元素，但不包含来自 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
}
}
}}

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

小开

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)..

小开

如果你想手动操作。基于气泡排序的解决方案(需要相同的长度) :

public void sortAbasedOnB(String[] listA, double[] listB) {
for (int i = 0; i < listB.length - 1; i++) {
for (int j = listB.length - 1; j > i; j--) {
if (listB[j] < listB[j - 1]){
double tempD = listB[j - 1];
listB[j - 1] = listB[j];
listB[j] = tempD;
String tempS = listA[j - 1];
listA[j - 1] = listA[j];
listA[j] = tempS;
}
}
}
}