Сортированная коллекция на Java

Question

Я новичок в Java. Пожалуйста, предложите, какую коллекцию (ы) можно / нужно использовать для поддержания отсортированного списка в Java. Я пробовал Map и Set, но это было не то, что я искал.

Answer 1

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

Answer 2

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

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

ех. для двоих:

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 (), а также имею дубликаты.

Answer 3

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

Answer 4

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

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

Answer 5

Сортировка ArrayList по заданным пользователем критериям.

Модель класса

 class Student 
 { 
     int rollno; 
     String name, address; 

     public Student(int rollno, String name, String address) 
     { 
         this.rollno = rollno; 
         this.name = name; 
         this.address = address; 
     }   

     public String toString() 
     { 
         return this.rollno + " " + this.name + " " + this.address; 
     } 
 } 

Класс сортировки

 class Sortbyroll implements Comparator<Student> 
 {         
     public int compare(Student a, Student b) 
     { 
         return a.rollno - b.rollno; 
     } 
 } 

Основной класс

 class Main 
 { 
     public static void main (String[] args) 
     { 
         ArrayList<Student> ar = new ArrayList<Student>(); 
         ar.add(new Student(111, "bbbb", "london")); 
         ar.add(new Student(131, "aaaa", "nyc")); 
         ar.add(new Student(121, "cccc", "jaipur")); 

         System.out.println("Unsorted"); 
         for (int i=0; i<ar.size(); i++) 
             System.out.println(ar.get(i)); 

         Collections.sort(ar, new Sortbyroll()); 

         System.out.println("\nSorted by rollno"); 
         for (int i=0; i<ar.size(); i++) 
             System.out.println(ar.get(i)); 
     } 
 } 

выход

 Unsorted
 111 bbbb london
 131 aaaa nyc
 121 cccc jaipur

 Sorted by rollno
 111 bbbb london
 121 cccc jaipur
 131 aaaa nyc

Answer 6

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

    }

}

Answer 7

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

Answer 8

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

Answer 9

Используйте метод 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