В Java, как вы сортируете один список на основе другого?

Ответ 1

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

Это довольно неэффективно, и вам, вероятно, следует создать Map<Item, Integer> из списка A, чтобы быстрее находить позиции элементов.

У Guava есть готовый к использованию компаратор для этого: Ordering.explicit()

Ответ 2

Java 8:

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

или лучше:

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

Ответ 3

Скажем, у вас есть список listB, который определяет порядок сортировки listA. Это всего лишь пример, но он демонстрирует порядок, который определяется списком, а не естественный порядок типа данных:

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

Теперь скажем, что listA нужно сортировать в соответствии с этим упорядочением. Это a 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));

Ответ 4

Улучшение скорости на 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);
        }
    });
}

Ответ 5

Вот решение, которое увеличивает временную сложность на 2n, но выполняет то, что вы хотите. Также не волнует, если List R, который вы хотите отсортировать, содержит элементы Comparable, если другой List L, который вы используете для сортировки, равномерно сопоставим.

public 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);. Теперь он действительно работает.

Ответ 6

Ниже приведен пример сортировки списка, а затем внесения изменений в другой список в соответствии с изменениями, внесенными в первый список массивов. Этот трюк никогда не будет терпеть неудачу и обеспечит сопоставление между элементами в списке. Размер обоих списков должен быть таким же, чтобы использовать этот трюк.

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

        });

    }

Ответ 7

Один из способов сделать это - перебирать через 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;

Ответ 8

Не совсем понятно, что вы хотите, но если это так: А: [с, Ь, а] Б: [2,1,0]

И вы хотите загрузить их оба, а затем произвести: С: [а, б, в]

Тогда, может быть, это?

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

Заметьте, я тоже не тестировал, может быть, знак перевернулся.

Ответ 9

Другим решением, которое может работать в зависимости от вашего параметра, является не сохранение экземпляров в listB, а вместо него индексы из списка. Это можно сделать, обернув 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 в настоящее время не позволяет добавить элемент из списка A второй раз - в этом отношении он фактически работает как набор элементов из списка A, потому что это обычно то, что вы хотите в такой настройке.

Предпочтительный способ добавить что-то в SortedDependingList - это уже знать индекс элемента и добавить его, вызвав sortedList.addByIndex(index);

Ответ 10

попробуйте это для java 8:

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

или

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

Ответ 11

Проблема: сортировка списка 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 ], [name = c, age = age33], [name = c, age = age3]]

Ответ 12

Если ссылки на объекты должны быть одинаковыми, вы можете инициализировать listA new.

listA = new ArrayList(listB)

Ответ 13

Как и Тим Херольд, если ссылки на объекты должны быть одинаковыми, вы можете просто скопировать listB в listA, либо:

listA = new ArrayList(listB);

Или это, если вы не хотите изменять список, список которого относится к:

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

Если ссылки не совпадают, но есть некоторая взаимосвязь эквивалентности между объектами в listA и listB, вы можете отсортировать listA с помощью пользовательского Comparator, который находит объект в listB и использует его индекс в listB как ключ сортировки. Наивное выполнение, которое переборная команда listB не будет лучшей по производительности, но будет функционально достаточной.

Ответ 14

ИМО, вам нужно упорствовать в чем-то еще. Может быть, не полный списокB, а что-то. Может быть просто указателями элементов, которые пользователь изменил.

Ответ 15

Попробуйте это. Код ниже является общим назначением для сценария, где 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);

Ответ 16

Просто столкнулся с той же проблемой.
У меня есть список упорядоченных ключей, и мне нужно заказать объекты в списке в соответствии с порядком ключей.
Мои списки достаточно длинны, чтобы сделать решения с временной сложностью 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.

Ответ 17

Чтобы избежать очень неэффективного поиска, вы должны проиндексировать элементы в 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));

Ответ 18

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]

Ответ 19

Если два списка гарантированно содержат одинаковые элементы, просто в разном порядке, вы можете использовать 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);
  }
});

Ответ 20

В Java есть набор классов, которые могут быть полезны для сортировки списков или массивов. В большинстве приведенных ниже примеров будут использоваться списки, но для массивов может применяться одна и та же концепция. Пример покажет это.

Мы можем использовать это, создав список целых чисел и отсортировав их с помощью Collections.sort(). Класс Collections (Java Doc) (часть Java Collection Framework) предоставляет список статических методов, которые мы можем использовать при работе с такими коллекциями, как список, набор и т.п. Итак, вкратце, мы можем отсортировать список, просто позвонив: java.util.Collections.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);
  }
}

Вышеприведенный класс создает список из четырех целых чисел и, используя метод сортировки коллекции, сортирует этот список (в одной строке кода) без необходимости беспокоиться об алгоритме сортировки.