常需要对list进行排序，小到List<String>，大到对自定义的类进行排序。不需要自行归并或堆排序。简单实现一个接口即可。
本文先会介绍利用Collections对List<String>进行排序，继而讲到Collections.sort的原理，
再讲到如何对自定义类进行排序，
最后会介绍利用Collections sort对自定义对象进行排序的另外一种方法，并将两种排序进行了简单的性能比较。
1、对List<String>排序及Collections.sort的原理
代码如下
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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实现
|
1
2
3
4
5
6
7
8
9
10
11
|
@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实现为
|
1
2
3
4
5
|
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中用于大小比较部分为
|
1
2
3
4
5
6
7
8
9
10
11
12
|
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定义
|
1
|
public final class Integer extends Number implements Comparable<Integer> |
再看下String的定义
|
1
|
public final class String implements java.io.Serializable, Comparable<String>, CharSequence |
我们可以发现他们都继承自Comparable
2.2 查看Comparable接口
可以发现Comparable中只有一个方法
Java代码
|
1
|
public int compareTo(T o); |
也就是说实际上binarySort方法中调用的是Comparable的compareTo方法，以此可知只要继承自Comparable，
并实现compareTo即可调用Collections.sort对自定义对象进行排序
2.3 自定义类的比较
下面代码为对User进行排序，首先按姓名字母先后排序，若姓名相同，则按年龄由小到大排序
Java代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
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; } } } |
执行后输出为：
Xml代码：
|
1
2
3
4
5
6
7
8
|
Herry 19Herry 20Jack 19James 18James 19Jim 19Luccy 19Lucy 19 |
可以看出只需两点即可
a、继承自Comparable
Java代码
|
1
|
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中的一样先比较姓名，若相等再比较年龄输出
Java代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
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; } } } |
可以看出其中
Java代码
|
1
|
Collections.sort(userList, new Comparator<User>()) |
为比较的主体，并且实现了Comparator的compare方法。下面介绍下此种方法的原理
追踪Collections的
Java代码
|
1
|
public static <T> void sort(List<T> list, Comparator<? super T> c) |
到
Java代码
|
1
|
public static <T> void sort(T[] a, Comparator<? super T> c) |
到
Java代码
|
1
|
private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off, Comparator c) |
可以发现其中代码如下：
Java代码
|
1
2
3
4
5
6
|
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排序原理就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持服务器之家。
