常需要对list进行排序，小到List<String>，大到对自定义的类进行排序。不需要自行归并或堆排序。简单实现一个接口即可。
本文先会介绍利用Collections对List<String>进行排序，继而讲到Collections.sort的原理，
再讲到如何对自定义类进行排序，
最后会介绍利用Collections sort对自定义对象进行排序的另外一种方法，并将两种排序进行了简单的性能比较。
下文中提到的如何追踪Collections等类的ava源代码，可以参考：http://trinea.iteye.com/blog/1351233
1、对List<String>排序及Collections.sort的原理
代码如下
List<String> stringList = new ArrayList<String>();
stringList.add("nice");
stringList.add("delicious");
stringList.add("able");
stringList.add("moon");
stringList.add("try");
stringList.add("friend");
Collections.sort(stringList);
for (String str : stringList) {
System.out.println(str);
}
其中Collections为java.util.Collections。
查看Collections中的sort实现
@SuppressWarnings("unchecked")
public static <T extends Comparable<? super T>> void sort(List<T> list) {
Object[] array = list.toArray();
Arrays.sort(array);
int i = 0;
ListIterator<T> it = list.listIterator();
while (it.hasNext()) {
it.next();
it.set((T) array[i++]);
}
}
从中可以看出排序主体为Arrays.sort(array);Arrays的sort实现为
public static void sort(Object[] array) {
// BEGIN android-changed
ComparableTimSort.sort(array);
// END android-changed
}
继续追踪，ComparableTimSort的sort实现ComparableTimSort.sort
static void sort(Object[] a)到static void sort(Object[] a, int lo, int hi)到private static void binarySort(Object[] a, int lo, int hi, int start)。在binarySort中用于大小比较部分为
Comparable<Object> pivot = (Comparable) a[start];
int left = lo;
int right = start;
assert left <= right;
while (left < right) {
int mid = (left + right) >>> 1;
if (pivot.compareTo(a[mid]) < 0)
right = mid;
else
left = mid + 1;
}
会调用Object的compareTo进行比较。而默认类似String和Integer类型都已经覆盖compareTo方法。所以可以自行进行比较
2、对自定义类进行比较
通过上面的介绍了解了Collections排序的原理，下面介绍下自定义对象的排序，先查看下Integer和String的比较原理、然后介绍如何对自定义类进行比较
2.1 我们查看Object的实现发现其中并没有compareTo方法，
再看下Integer定义
public final class Integer extends Number implements Comparable<Integer>
再看下String的定义
public final class String implements java.io.Serializable, Comparable<String>, CharSequence
我们可以发现他们都继承自Comparable
2.2 查看Comparable接口
可以发现Comparable中只有一个方法
public int compareTo(T o);
也就是说实际上binarySort方法中调用的是Comparable的compareTo方法，以此可知只要继承自Comparable，
并实现compareTo即可调用Collections.sort对自定义对象进行排序
2.3 自定义类的比较
下面代码为对User进行排序，首先按姓名字母先后排序，若姓名相同，则按年龄由小到大排序
public class MainTest {
public static void main(String[] args) {
List<User> userList = new ArrayList<User>();
userList.add(new User("Lucy", 19));
userList.add(new User("Jack", 19));
userList.add(new User("Jim", 19));
userList.add(new User("James", 19));
userList.add(new User("Herry", 19));
userList.add(new User("Luccy", 19));
userList.add(new User("James", 18));
userList.add(new User("Herry", 20));
Collections.sort(userList);
for (User user : userList) {
System.out.println(user.getName() + "\t\t" + user.getAge());
}
}
private static class User implements Comparable<User> {
private String name;
private int age;
public User(String name, int age){
this.name = name;
this.age = age;
}
@Override
public int compareTo(User another) {
int compareName = this.name.compareTo(another.getName());
if (compareName == 0) {
return (this.age == another.getAge() ? 0 : (this.age > another.getAge() ? 1 : -1));
}
return compareName;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
}
}
执行后输出为：
Herry 19 Herry 20 Jack 19 James 18 James 19 Jim 19 Luccy 19 Lucy 19
可以看出只需两点即可
a、继承自Comparable
private static class User implements Comparable<User>
b、实现compareTo方法
上面的public int compareTo(User another)为比较的主体
可以看到其中int compareName = this.name.compareTo(another.getName());表示比较姓名
若大于返回1，等于返回0，小于会返回-1。
若相等则按照int age的大小进行比较。
上面的大于返回1，等于返回0，小于会返回-1也是用来binarySort比较的依据。
3、利用Collections sort的重载函数对自定义对象进行排序
代码如下，仍同2中的一样先比较姓名，若相等再比较年龄输出
public class MainTest {
public static void main(String[] args) {
List<User> userList = new ArrayList<User>();
userList.add(new User("Lucy", 19));
userList.add(new User("Jack", 19));
userList.add(new User("Jim", 19));
userList.add(new User("James", 19));
userList.add(new User("Herry", 19));
userList.add(new User("Luccy", 19));
userList.add(new User("James", 18));
userList.add(new User("Herry", 20));
Collections.sort(userList, new Comparator<User>() {
public int compare(User user1, User user2) {
int compareName = user1.getName().compareTo(user2.getName());
if (compareName == 0) {
return (user1.getAge() == user2.getAge() ? 0 : (user1.getAge() > user2.getAge() ? 1 : -1));
}
return compareName;
}
});
for (User user : userList) {
System.out.println(user.getName() + "\t\t" + user.getAge());
}
}
private static class User {
private String name;
private int age;
public User(String name, int age){
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
}
}
可以看出其中
Collections.sort(userList, new Comparator<User>())
为比较的主体，并且实现了Comparator的compare方法。下面介绍下此种方法的原理
追踪Collections的
public static <T> void sort(List<T> list, Comparator<? super T> c)
到
public static <T> void sort(T[] a, Comparator<? super T> c)
到
private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off, Comparator c)
可以发现其中代码如下：
if (length < INSERTIONSORT_THRESHOLD) {
for (int i=low; i<high; i++)
for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
swap(dest, j, j-1);
return;
}
调用Comparator的compare方法
4、以上两种排序性能的比较
binarySort需要进行nlg(n)次的比较，最坏情况下n^2次的移动
mergeSort是不断进行二分，二分到很小部分后进行插入排序。所以会比较nlg(n)次，移动nlg(n)次。但它需要先复制一份源数据，所以会多占用一倍的空间
所以实际情况可以根据需要选择
相关推荐
本篇文章将探讨如何对对象数组或List进行排序，以及Collections排序的底层原理。 首先，我们关注`List<String>`的排序。对于一个包含字符串的列表，我们可以使用`Collections.sort()`方法来轻松实现排序。以下是一...
在Java编程语言中，ArrayList是集合框架的一部分，属于List接口的实现类，它是一个动态数组，可以存储可变数量的对象。当我们说“arraylist对象中的某个值排序”时，这通常指的是对ArrayList中的元素，而不是...
对于大型数据集，`Collections.sort()`通常能提供很好的性能，但如果需要对大量不可变对象或已排序的列表进行排序，使用`TreeSet`或`LinkedHashSet`等集合类型可能会更高效，因为它们在底层实现了红黑树结构，插入和...
在Java编程中，大作业通常涉及实际应用中的问题解决，这次的任务是利用数组实现一个队列排序，并且能够动态地插入新的元素。这个任务主要涵盖了两个核心知识点：数组的使用和排序算法。下面将详细解释这两个方面。 ...
这个方法是通过.NET框架中的`System.Collections.Generic`命名空间下的`List<T>`类提供的，同时也存在于`Array`类中。本篇文章将深入探讨如何使用`Sort`方法对数组进行快速排序以及其背后的实现原理。 首先，让我们...
虽然Java 5.0的`Arrays.sort()`方法不能直接用于多维数组，但可以通过递归或循环的方式，对二维数组的每一行进行单独排序。 四、`Collections.sort()`与`List` 除了`Arrays.sort()`，Java 5.0的`Collections.sort...
泛型集合如`List<T>`提供了与`ArrayList`类似的功能，但`T`代表一个类型参数，可以在实例化时指定，如`List<int>`或`List<string>`。这确保了集合内的所有元素都是同一类型，从而避免了类型检查和装箱/拆箱操作，...
这样做的目的是因为 `Collections.sort()` 方法直接对 `List` 接口的实现进行排序，而不是数组。 2. **线程安全的 List**：`List list = Collections.synchronizedList(al);` 这行代码将 `ArrayList` 转换为线程...
通过对`List<T>`类的排序方法的学习，我们可以灵活地对不同类型的对象进行排序。通过自定义比较器，我们可以实现更复杂的排序逻辑。此外，`List<T>`还支持部分排序，进一步增强了排序功能的灵活性。理解并掌握这些...
本文将深入探讨如何对ArrayList、HashSet、TreeSet以及数组中的对象进行排序。理解这些排序机制对于编写高效且可维护的代码至关重要。 首先，让我们从ArrayList开始。ArrayList是Java中实现List接口的一个动态数组...
在C#编程语言中，ArrayList是一个非常常用的动态数组类，它是System.Collections命名空间的一部分。ArrayList提供了灵活的容量扩展和操作，但与固定大小的一维数组相比，它在内存管理和性能方面有所不同。本篇文章将...
它可以对任何类型的对象数组进行排序，只要该类型实现了`Comparable`接口或者提供了自定义的`Comparator`。例如，对于整数数组： ```java int[] numbers = {5, 3, 9, 1, 7}; Arrays.sort(numbers); ``` 如果需要...
本文档将详细讲解如何通过对象的一个或多个属性来实现对象的排序，并支持正序与倒序排序。 #### 一、项目位置 本项目的包名为 `packagecom.mpt.util.`，类名为 `ComparatorUtil`。这个类提供了用于根据对象的属性...
本文实例分析了C#数组反转与排序的方法。分享给大家供大家参考。具体实现方法如下： C#数组反转 代码如下:using System; using System.Collections.Generic; using System.Linq; using System.Text; ...
在Java编程语言中，对象排序是一项常见的操作，特别是在处理数据结构如数组或集合时。`java sort`标签表明我们关注的是使用Java内置的排序机制。本文将深入探讨Java中的对象排序，包括基本概念、API使用以及自定义...
也可以通过泛型对对象类型的数组排序，但需要数组元素实现了`Comparable`接口。例如： ```java int[] numbers = {5, 2, 8, 1, 9}; Arrays.sort(numbers); ``` 2. 对于自定义排序规则，可以使用`Collections....
`Collections.shuffle()`方法位于`java.util.Collections`类中，它接受一个`List`类型的参数，并对其进行原地排序。这意味着它不会创建新的列表，而是直接修改输入的列表，将元素的顺序随机打乱。源码如下： ```...
// 对List排序 List<Integer> list = Arrays.asList(5, 3, 8, 1, 9); Collections.sort(list); System.out.println(list); // 使用Comparator自定义排序规则 List<Person> people = Arrays.asList( new ...
- 在方法签名中，数组被视为对象，因此可以作为参数传递。在方法内部，数组是可变的，可以修改其元素。 8. **动态数组ArrayList**： - 虽然基本类型的数组长度固定，但可以使用`ArrayList`类创建动态大小的数组。...