logo标签列表

Java中的排序集合

javasortingcollections
169

我是Java的初学者，请建议在Java中用哪些集合（集合）来维护有序列表。我尝试过 Map 和 Set ，但它们不是我想要的。

21个回答
4

使用LambdaJ

如果您正在使用Java 8之前的版本，可以尝试使用LambdaJ来解决这些任务。您可以在此处找到它：http://code.google.com/p/lambdaj/

以下是一个示例：

迭代排序

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倍），但你能否找到更易读的代码呢？

使用Lambda表达式在Java 8中进行排序

Collections.sort(persons, (p1, p2) -> p1.getAge().compareTo(p2.getAge()));
//or
persons.sort((p1, p2) -> p1.getAge().compareTo(p2.getAge()));
在您最后一个使用Java 8 Lambda表达式的示例中，如何进行反向排序？ - Rajat Shah
1
@RajatShah 我想你可以直接使用 -(p1.getAge().compareTo(p2.getAge())) - Federico Piazza
@RajatShah 很高兴能帮助。 - Federico Piazza
3
你可以使用TreeSet来进行集合排序。TreeSet会根据元素的自然顺序或传递给特定对象的Comparable接口的任何排序顺序对其进行排序。 对于Map，请使用TreeMap。TreeMap提供了按键进行排序的功能。要将一个对象添加为TreeMap的键，该类应实现可比接口，从而强制实现compare to()方法，该方法包含排序顺序的定义。 最初的回答：http://techmastertutorial.in/java-collection-impl.html
2

PriorityQueue的问题在于它由一个简单的数组支持，并且通过 "queue[2*n+1] and queue[2*(n+1)]" 进行排序元素的逻辑。如果你只从头部提取元素，它的效果非常好，但是如果你试图在某个时候调用.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()时按顺序获取值，并且保留重复项。
1

按用户定义的标准对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
1

为什么不亲手制作呢？

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Random;

class SortedList<E extends Comparable<E>> extends ArrayList<E> {
    @Override
    public boolean add(E e) {
        int i = Collections.binarySearch(this, e);

        if (i < 0) i = ~i;
        super.add(i, e);
        return true;
    } // add(E e)

    @Override
    public void add(int index, E element) {
        this.add(element);
    } // add(int, E)

    @Override
    public boolean addAll(Collection<? extends E> c) {
        int oldSize = this.size();

        for (E element : c) this.add(element);
        return oldSize != this.size();
    } // addAll(Collection<? extends E>)

    @Override
    public boolean addAll(int index, Collection<? extends E> c) {
        int oldSize = this.size();
        Iterator<? extends E> it = c.iterator();

        for (int i = 0; i < index; ++i) it.next();
        while (it.hasNext()) this.add(it.next());
        return oldSize != this.size();
    } // addAll(Collection<? extends E>)

    @Override
    public E set(int index, E element) {
        E ret = this.get(index);

        this.remove(index);
        this.add(element);
        return ret;
    } // set(int, E)
} // SortedList<E> Class

public class Solution {
    public static void main(String[] args) {
        Random r = new Random(1);
        List<Integer> sortedList = new SortedList<>();
        List<Integer> unsortedList = new ArrayList<>();

        for (int i = 0; i < 50; ++i) {
            int next = r.nextInt(1000);

            sortedList.add(next);
            unsortedList.add(next);
        } // for (int i = 0; i < 50; ++i)

        System.out.println("unsortedList:");
        System.out.println(unsortedList);
        System.out.println("\nsortedList:");
        System.out.println(sortedList);
        sortedList.clear();
        sortedList.addAll(unsortedList);
        System.out.println("\ntest for addAll(Collection) method:");
        System.out.println(sortedList);
        sortedList.clear();
        sortedList.addAll(30, unsortedList);
        System.out.println("\ntest for addAll(int, Collection) method:");
        System.out.println(sortedList);
        sortedList.set(0, 999);
        System.out.println("\ntest for set(int, E) method:");
        System.out.println(sortedList);
    } // main(String[])
} // Solution Class

输出：

unsortedList:
[985, 588, 847, 313, 254, 904, 434, 606, 978, 748, 569, 473, 317, 263, 562, 234, 592, 262, 596, 189, 376, 332, 310, 99, 674, 959, 298, 153, 437, 302, 205, 854, 800, 6, 363, 955, 689, 820, 75, 834, 415, 660, 477, 737, 477, 592, 220, 888, 500, 357]

sortedList:
[6, 75, 99, 153, 189, 205, 220, 234, 254, 262, 263, 298, 302, 310, 313, 317, 332, 357, 363, 376, 415, 434, 437, 473, 477, 477, 500, 562, 569, 588, 592, 592, 596, 606, 660, 674, 689, 737, 748, 800, 820, 834, 847, 854, 888, 904, 955, 959, 978, 985]

test for addAll(Collection) method:
[6, 75, 99, 153, 189, 205, 220, 234, 254, 262, 263, 298, 302, 310, 313, 317, 332, 357, 363, 376, 415, 434, 437, 473, 477, 477, 500, 562, 569, 588, 592, 592, 596, 606, 660, 674, 689, 737, 748, 800, 820, 834, 847, 854, 888, 904, 955, 959, 978, 985]

test for addAll(int, Collection) method:
[6, 75, 205, 220, 357, 363, 415, 477, 477, 500, 592, 660, 689, 737, 800, 820, 834, 854, 888, 955]

test for set(int, E) method:
[75, 205, 220, 357, 363, 415, 477, 477, 500, 592, 660, 689, 737, 800, 820, 834, 854, 888, 955, 999]
1
您可以使用ArrayList和TreeMap，正如您所说，如果您需要重复的值，则不能使用TreeSet，尽管它也是有序的，但您必须定义比较器。
1
你需要的是一个二叉搜索树。它可以在保持排序顺序的同时，提供对搜索、删除和插入的对数级访问（除非你有一个退化的树——那么它就是线性的）。它很容易实现，甚至可以使它实现List接口，但是索引访问会变得复杂。
第二种方法是使用ArrayList，然后使用冒泡排序实现。因为你每次只插入或删除一个元素，所以插入和删除的访问时间是线性的。搜索是对数级的，索引访问是常数级的（对于LinkedList可能会有不同的时间）。你只需要5或6行冒泡排序的代码即可。
0
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);    
}
0
使用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);

    }

}
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接