用 Java 对集合进行排序

我是爪哇初学者。请说明哪些集合可以/应该用于在 Java 中维护已排序的列表。我试过 Map和 Set，但它们不是我想要的。

213842 次浏览
小开

TreeMap 和 TreeSet 将按照排序顺序对内容进行迭代。或者可以使用 ArrayList 并使用 Collections.sort ()对其进行排序。所有这些类都在 java.util 中

小开

您需要 整理好了实现，即 树集。

小开

有一些选项。我建议 TreeSet，如果你不想要重复的对象和你正在插入的对象是可比较的。

还可以使用 Collectionsclass 的静态方法来完成这项工作。

有关更多信息，请参见 集合 # sort (java.util.List)和 树集。

小开

如果只想对列表进行排序，可以使用任何类型的 名单并使用 Collections.sort ()。如果希望确保列表中的元素是唯一的并且始终排序，请使用 整理好了。

小开

如果你想保持一个 分类清单，你将 经常修改(即一个结构，除了被排序，允许重复，其元素可以有效地引用索引) ，然后使用数组列表，但是当你需要插入一个元素，始终使用 BinarySearch ()来确定索引，你添加一个给定的元素。后一种方法告诉您需要插入的索引位置，以保持列表的排序顺序。

小开

这很晚才发生，但是 JDK 中有一个类只是为了有一个已排序的列表。它被命名为“ java.util.PriorityQueue”(与其他 Sorted*接口有些不同)。它既可以对 Comparable<?>进行排序，也可以使用 Comparator进行排序。

与使用 Collections.sort(...)排序的 List的不同之处在于，通过使用堆数据结构，List将始终保持部分顺序，具有 O (log (n))插入性能，而在排序的 ArrayList中插入将为 O (n)(即使用二进制搜索和移动)。

但是，与 List不同，PriorityQueue不支持索引访问(get(5))和 访问堆中项的唯一方法是一次取出一个项(因此称为 PriorityQueue)。

小开

使用 GoogleGuava 的 TreeMultiset类。

提供一个保持排序顺序的 List 实现的一个问题是在 add()方法的 JavaDocs 中做出的承诺。

小开

TreeSet 不能工作，因为它们不允许重复，而且它们不提供在特定位置获取元素的方法。PriorityQueue 不能工作，因为它不允许在特定位置获取元素，而这是列表的基本要求。 我认为您需要实现自己的算法，以便在 Java 中用 O (logn)插入时间维护排序列表，除非您不需要重复。 也许解决方案可以使用 TreeMap，其中键是项的子类，该子类覆盖 equals 方法，因此允许重复。

小开

你想要的是二叉查找树。它维护排序顺序，同时提供对数访问的搜索，删除和插入(除非你有一个退化的树-那么它的线性)。它很容易实现，甚至可以让它实现 List 接口，但是索引访问会变得很复杂。

第二种方法是使用数组列表，然后使用冒泡排序实现。因为一次插入或删除一个元素，所以插入和删除的访问时间是线性的。搜索是对数和索引访问常数(对于 LinkedList，时间可能会有所不同)。您需要的唯一代码是5行，也许是6行冒泡排序。

小开

我所做的就是实现 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);
}

之后，我实现了一个新方法“ putOrded”，它在元素不存在时插入到正确的位置，或者在元素存在时替换它。

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

如果您想要允许重复的元素，那么只需要实现 addOrded (或者两者都实现)。

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

如果希望避免插入，还可以在“ add”和“ set”方法上抛出和不支持的操作异常。

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

... 而且您还必须小心使用 ListIterator 方法，因为它们可能会修改您的内部列表。在这种情况下，您可以返回内部列表的副本，或者再次引发异常。

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

使用 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()));
小开

PriorityQueue 的问题在于它是由一个简单的数组备份的，而按顺序获取元素的逻辑是由“ queue [2 * n + 1]和 queue [2 * (n + 1)]”之类的东西完成的。它工作得很好，如果你只是从头拉，但使它无用，如果你试图调用。在某个点上进行数组。

我通过使用 com.google.common.Collection 来解决这个问题。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 ()时，就可以按顺序得到值，并且还有重复的值。

小开

你可以使用 Arraylist 和 Treemap，正如你说你想要重复的值，然后你不能使用 TreeSet，虽然它也是有序的，但是你必须定义比较器。

小开

使用 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

小开

实现您想要的排序列表的最有效方法是实现一个可索引的 Skiplist，如下所示: Wikipedia: Indexable skiplist 维基百科: 可索引的跳过程序。 它允许在 O (log (n))中进行插入/删除操作，并允许同时进行索引访问。它还允许复制。

Skiplist 是一个非常有趣的数据结构，我认为它被低估了。 不幸的是，在 Java 基础库中没有索引 Skiplist 实现，但是您可以使用开源实现之一或者自己实现它。有一些常规的 Skiplist 实现，比如 ConcurrentSkipListSet和 < a href = “ https://docs.oracle.com/javase/7/docs/api/java/util/concurrentSkipListMap.html”rel = “ nofollow norefrer”> ConcurrentSkipListMap

小开

使用按顺序排列的 TreeSet，或者使用 Collection.sort()来表示与 Comparator()一起排列的外排序。

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

使用 Java8的比较器，如果我们想要排序列表，那么这里是世界上人口最多的10个城市，我们想要按名字排序，正如时代周刊报道的那样。 日本大阪... 墨西哥城，墨西哥..。 中国北京... ... 巴西圣保罗... ... 印度孟买... ... 上海... .., 中国，德里，印度，东京，日本。

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


}


}
小开

根据用户定义的条件对数组列表进行排序。

模型班

 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
小开

对于 Set，可以使用 TreeSet。TreeSet 根据自然顺序或传递给该特定对象的 Compaable 的任何排序顺序对其元素进行排序。 地图使用 TreeMap。TreeMap 提供了键的排序。为了向 TreeMap 添加一个对象作为键，该类应该实现可比接口，这又强制实现包含排序顺序定义的比较()方法。 Http://techmastertutorial.in/java-collection-impl.html

小开

为什么不自己做呢？

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]

提交答案