Сортировка списков Java: есть ли способ сохранить список автоматически отсортированным, как TreeMap?

Question

В Java вы можете создать ArrayList с элементами, а затем вызвать:

Collections.sort(list, comparator);

Есть ли способ передать Comparator во время списка, создание, как вы можете сделать с TreeMap?

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

Есть ли способ достичь этого таким способом с помощью Comparator или каким-либо другим аналогичным способом?

Answer 1

Единственный способ добавить к элементу / indexOf / remove / get любую отсортированную структуру с временем, меньшим O (n), - это использовать дерево.В этом случае операции обычно имеют O (log2n), а ход - как O (1).

O (n) - это просто связанный список.

---

Редактирование: вставка в связанный списокж / бинарный поиск.Для операций вставки, не использующих двоичную структуру и не небольших размеров, это должно быть оптимальным.

@ Peter: Существует алгоритм w / O (log2n), который сравнивает (которые являются медленными) вставку и O (n) движется.Если вам нужно переопределить LinkedList, пусть будет так.Но это настолько опрятно, насколько это возможно.Я держу алгоритм настолько чистым, насколько это возможно, чтобы его было легко понять, его можно немного оптимизировать.

package t1;

import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;

public class SortedList {


    private static <T> int binarySearch(ListIterator<? extends Comparable<? super T>> i, T key){
        int low = 0;
        int high= i.previousIndex();
        while (low <= high) {
            int mid = (low + high) >>> 1;
            Comparable<? super T> midVal = get(i, mid);
            int cmp = midVal.compareTo(key);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid;
        }
        return -(low + 1);  // key not found
    }

    private static <T> T get(ListIterator<? extends T> i, int index) {
        T obj = null;
        int pos = i.nextIndex();
        if (pos <= index) {
            do {
                obj = i.next();
            } while (pos++ < index);
        } else {
            do {
                obj = i.previous();
            } while (--pos > index);
        }
        return obj;
    }
    private static void move(ListIterator<?> i, int index) {        
        int pos = i.nextIndex();
        if (pos==index)
            return;

        if (pos < index) {
            do {
                i.next();
            } while (++pos < index);
        } 
        else {
            do {
                i.previous();
            } while (--pos > index);
        }
    }
    @SuppressWarnings("unchecked")
    static  <T> int insert(List<? extends Comparable<? super T>> list, T key){
        ListIterator<? extends Comparable<? super T>> i= list.listIterator(list.size());
        int idx = binarySearch(i, key); 
        if (idx<0){
            idx=~idx;
        }
        move(i, idx);
        ((ListIterator<T>)i).add(key);
        return i.nextIndex()-1;
    }

    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        LinkedList<Integer> unsorted = new LinkedList<Integer>();
        Random r =new Random(11);
        for (int i=0;i<33;i++){
            Integer n = r.nextInt(17);
            insert(list, n);
            unsorted.add(n);            
        }

        System.out.println("  sorted: "+list);
        System.out.println("unsorted: "+unsorted);
    }

Answer 2

SortedSet

Любая реализация интерфейса SortedSet несет желаемое поведение.

По умолчанию добавленные объекты сортируются в естественном порядке, то есть на основе реализации метода интерфейса Comparable::compareTo.

В качестве альтернативы вы можете передать реализацию Comparator, чтобы определить сортировку.

TreeSet

TreeSet - это обычно используемая имплантация SortedSet. Вы также можете найти других.

Дубликаты

Основное различие между List и SortedSet - это дубликаты, объекты, которые сравниваются как равные. List допускает дублирование, а SortedSet, как и любой Set, - нет.

Доступ по индексу

Другое отличие состоит в том, что Set не может быть доступен по индексу. Вы не можете найти объект по номеру позиции в коллекции.

Если вам нужен такой доступ после создания вашего SortedSet, сделайте List. Есть несколько способов сделать это, например, передать SortedSet в конструктор ArrayList. Самым недавним способом, начиная с Java 10, является сделать немодифицируемым List, передав SortedSet в List.copyOf.

Answer 3

Контракт интерфейса ListIterator делает его немного громоздким, но этот метод будет выполнять вставку с использованием одного сканирования списка (до точки вставки):

private void add(Integer value) {
    ListIterator<Integer> listIterator = list.listIterator();

    Integer next = null;

    while (listIterator.hasNext()) {
        next = listIterator.next();

        if (next.compareTo(value) > 0) {                
            break;
        }
    }

    if (next == null || next.compareTo(value) < 0) {
        listIterator.add(value);
    } else {
        listIterator.set(value);
        listIterator.add(next);
    }
}

Answer 4

Лучший способ сделать это - переопределить реализацию добавления списка. Я собираюсь использовать LinkedList, чтобы продемонстрировать это, так как он обеспечивает эффективную вставку.

public boolean add(Integer e)
{
    int i = 0;
    for (Iterator<Integer> it = this.iterator(); it.hasNext();)
    {
        int current = it.next();
        if(current > e)
        {
            super.add(i, e);
            return true;
        }
        i++;
    }
    return super.add(e);
}

Приведенный выше код создает отсортированный список целых чисел, который всегда сортируется. Его можно легко изменить для работы с любым другим типом данных. Однако здесь вам придется избегать использования функции add(index, value), поскольку это, очевидно, нарушит сортировку.

Хотя люди выше предложили использовать Arrays.sort (), я бы избегал этого, так как это может быть значительно менее эффективный подход, тем более что метод сортировки должен вызываться при каждом добавлении в список.

Answer 5

Я полагаю, что Очередь приоритетов выполнит эту работу.

Предупреждение (с той же страницы документа):

Этот класс и его итератор реализуют все необязательные методы Collection и интерфейсы итераторов. Iterator предоставлено в методе iterator() не гарантируется пройти элементы приоритета очередь в любом конкретном порядке. если ты нужно упорядоченное прохождение, рассмотрите возможность использования Arrays.sort(pq.toArray()).