Это происходит очень поздно, но в JDK есть класс только для того, чтобы иметь отсортированный список. Он назван (несколько не в порядке с другими интерфейсами Sorted*) "java.util.PriorityQueue". Он может сортировать либо Comparable<?> s, либо использовать Comparator.

Разница с List, отсортированная с использованием Collections.sort(...), заключается в том, что это будет поддерживать частичный порядок в любое время, с O (log (n)) с использованием структуры данных кучи, тогда как вставка в отсортированном ArrayList будет O (n) (т. е. с использованием двоичного поиска и перемещения).

Однако, в отличие от List, PriorityQueue не поддерживает индексированный доступ (get(5)), единственный способ получить доступ к элементам в куче - это вынуть их по одному (таким образом, имя PriorityQueue).

То, что я сделал, это реализовать List с внутренним экземпляром со всеми делегированными методами.

 public class ContactList implements List<Contact>, Serializable {
    private static final long serialVersionUID = -1862666454644475565L;
    private final List<Contact> list;

public ContactList() {
    super();
    this.list = new ArrayList<Contact>();
}

public ContactList(List<Contact> list) {
    super();
    //copy and order list
    List<Contact>aux= new ArrayList(list);
    Collections.sort(aux);

    this.list = aux;
}

public void clear() {
    list.clear();
}

public boolean contains(Object object) {
    return list.contains(object);
}

После этого я внедрил новый метод «putOrdered», который вставляет правильную позицию, если элемент не существует или заменяется на всякий случай, если он существует.

public void putOrdered(Contact contact) {
    int index=Collections.binarySearch(this.list,contact);
    if(index<0){
        index= -(index+1);
        list.add(index, contact);
    }else{
        list.set(index, contact);
    }
}

Если вы хотите, чтобы повторяющиеся элементы просто реализовали addOrdered (или оба).

public void addOrdered(Contact contact) {
    int index=Collections.binarySearch(this.list,contact);
    if(index<0){
        index= -(index+1);
    }
    list.add(index, contact);
}

Если вы хотите избежать вложений, вы также можете исключить и исключить операцию неподдерживаемой операции в методах «добавить» и «установить».

public boolean add(Contact object) {
    throw new UnsupportedOperationException("Use putOrdered instead");
}

... а также вы должны быть осторожны с методами ListIterator, потому что они могут изменить ваш внутренний список. В этом случае вы можете вернуть копию внутреннего списка или снова выбросить исключение.

public ListIterator<Contact> listIterator() {
    return (new ArrayList<Contact>(list)).listIterator();
}

Вы хотите реализовать SortedSet , а именно TreeSet .

Использовать TreeMultiset Google Guava. Guava - впечатляющий набор API.

Guava: https://github.com/google/guava

TreeMultiset: https: // google.github.io/guava/releases/snapshot/api/docs/com/google/common/collect/TreeMultiset.html

Одна проблема с предоставлением реализации списка, который поддерживает отсортированный порядок это обещание, сделанное в Javadocs метода 'add'.

Использование LambdaJ

Вы можете попробовать решить эти задачи с помощью LambdaJ, если вы используете предыдущие версии для java 8. Вы можете найти его здесь: http://code.google.com/p / lambdaj /

Здесь у вас есть пример:

Сортировать Iterative

List<Person> sortedByAgePersons = new ArrayList<Person>(persons);
Collections.sort(sortedByAgePersons, new Comparator<Person>() {
        public int compare(Person p1, Person p2) {
           return Integer.valueOf(p1.getAge()).compareTo(p2.getAge());
        }
}); 

Сортировать по LambdaJ

List<Person> sortedByAgePersons = sort(persons, on(Person.class).getAge()); 

Конечно, такая красота влияет на производительность (в среднем 2 раза), но вы можете найти более читаемый код?

Сортировка с java 8 с использованием лямбда-выражения

Collections.sort(persons, (p1, p2) -> p1.getAge().compareTo(p2.getAge()));
//or
persons.sort((p1, p2) -> p1.getAge().compareTo(p2.getAge()));

TreeSet не работает, потому что они не позволяют дублировать, и они не предоставляют метод для извлечения элемента в определенной позиции. PriorityQueue не будет работать, потому что он не позволяет получать элементы в определенной позиции, что является основным требованием для списка. Я думаю, вам нужно реализовать собственный алгоритм для поддержки отсортированного списка в Java с временем вставки O (logn), если вам не нужны дубликаты. Возможно, решение может использовать TreeMap, где ключ является подклассом элемента, переопределяющим метод equals, так что дубликаты разрешены.

Если вы хотите просто отсортировать список, используйте любой List и используйте Collections.sort () . Если вы хотите убедиться, что элементы в списке уникальны и всегда отсортированы, используйте SortedSet .

Используйте метод sort () для сортировки списка, как показано ниже:

List list = new ArrayList();

//add elements to the list

Comparator comparator = new SomeComparator();

Collections.sort(list, comparator);

Для справки см. ссылку: http://tutorials.jenkov.com/java-collections/sorting. HTML

Что вы хотите, это двоичное дерево поиска. Он поддерживает упорядоченный порядок, предлагая логарифмический доступ для поиска, удаления и вставки (если у вас нет вырожденного дерева, а затем оно линейно). Это довольно просто реализовать, и вы даже можете заставить его реализовать интерфейс List, но тогда индексный доступ становится сложным.

Второй подход заключается в том, чтобы иметь ArrayList, а затем реализацию сорта пузырьков. Поскольку вы вставляете или удаляете один элемент за раз, время доступа для вставок и абзацев является линейным. Поиски являются логарифмическими и постоянными доступа к индексу (времена могут быть разными для LinkedList). Единственный код, который вам нужен, - 5, может быть, 6 строк пузырьковой сортировки.

Есть несколько вариантов. Я бы предложил TreeSet, если вы не хотите, чтобы дубликаты и объекты, которые вы вставляете, сопоставимы.

Вы также можете использовать статические методы класса Collections.

См. Коллекции # sort (java.util.List) и TreeSet для получения дополнительной информации.

Проблема с PriorityQueue заключается в том, что она подкрепляется простым массивом, а логика, которая получает упорядоченные элементы, выполняется «queue [2 * n + 1] и queue [2 * (n + 1)] "thingie. Он отлично работает, если вы просто тянете с головы, но делает его бесполезным, если вы пытаетесь в какой-то момент называть .toArray.

Я обойду эту проблему, используя com.google.common.collect.TreeMultimap, но я поставляю собственный Компаратор для значений, завернутых в Ordering, который никогда не возвращает 0.

ех. для Double:

private static final Ordering<Double> NoEqualOrder = Ordering.from(new Comparator<Double>() {

    @Override
    public int compare(Double d1, Double d2)
    {
        if (d1 < d2) {
            return -1;
        }
        else {
            return 1;
        }
    }
});

Таким образом, я получаю значения в порядке, когда я вызываю .toArray (), а также имеет дубликаты.

Используйте TreeSet, который дает элементы в отсортированном порядке. ИЛИ используйте Collection.sort() для внешней сортировки с Comparator().

TreeMap и TreeSet предоставят вам итерацию по содержимому в отсортированном порядке. Или вы можете использовать ArrayList и использовать Collections.sort () для его сортировки. Все эти классы находятся в java.util

Если вы хотите сохранить отсортированный список, который вы часто будете изменять (т. е. структуру, которая, помимо сортировки, позволяет дублировать и чьи элементы можно эффективно ссылать на индекс), затем используйте ArrayList, но когда вам нужно вставьте элемент, всегда используйте Collections.binarySearch (), чтобы определить индекс, в который вы добавляете данный элемент. Последний метод сообщает вам индекс, который вам нужно вставить, чтобы сохранить список в отсортированном порядке.

import java.util.TreeSet;

public class Ass3 {
    TreeSet<String>str=new TreeSet<String>();
    str.add("dog");
    str.add("doonkey");
    str.add("rat");
    str.add("rabbit");
    str.add("elephant");
    System.out.println(str);    
}

Вы можете использовать Arraylist и Treemap, так как вы сказали, что хотите повторять значения, но тогда вы не можете использовать TreeSet, хотя он также отсортирован, но вы должны определить компаратор.

с Java 8 Comparator, если мы хотим отсортировать список, то вот 10 самых населенных городов в мире, и мы хотим отсортировать их по названию, как сообщает Time. Осака, Япония. ... Мехико, Мексика. ... Пекин, Китай. ... Сан-Паулу, Бразилия. ... Мумбаи, Индия. ... Шанхай, Китай. ... Дели, Индия. ... Токио, Япония.

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

public class SortCityList {

    /*
     * Here are the 10 most populated cities in the world and we want to sort it by
     * name, as reported by Time. Osaka, Japan. ... Mexico City, Mexico. ...
     * Beijing, China. ... São Paulo, Brazil. ... Mumbai, India. ... Shanghai,
     * China. ... Delhi, India. ... Tokyo, Japan.
     */
    public static void main(String[] args) {
        List<String> cities = Arrays.asList("Osaka", "Mexico City", "São Paulo", "Mumbai", "Shanghai", "Delhi",
                "Tokyo");
        System.out.println("Before Sorting List is:-");
        System.out.println(cities);
        System.out.println("--------------------------------");

        System.out.println("After Use of List sort(String.CASE_INSENSITIVE_ORDER) & Sorting List is:-");
        cities.sort(String.CASE_INSENSITIVE_ORDER);
        System.out.println(cities);
        System.out.println("--------------------------------");
        System.out.println("After Use of List sort(Comparator.naturalOrder()) & Sorting List is:-");
        cities.sort(Comparator.naturalOrder());
        System.out.println(cities);

    }

}

Самый эффективный способ реализовать отсортированный список, как вы хотите, - это реализовать индексируемый скипист, как здесь: Wikipedia: Indexable skiplist . Это позволило бы иметь вставки / удаления в O (log (n)) и позволяло бы иметь индексированный доступ в одно и то же время. И это также позволило бы дублировать.

Skiplist - довольно интересная и, я бы сказал, недооцененная структура данных. К сожалению, в библиотеке баз данных Java нет реализации skiplist, но вы можете использовать одну из реализаций с открытым исходным кодом или реализовать ее самостоятельно.