浅谈对象数组或list排序及Collections排序原理
常需要对list进行排序，小到list<string>，大到对自定义的类进行排序。不需要自行归并或堆排序。简单实现一个接口即可。
本文先会介绍利用collections对list<string>进行排序，继而讲到collections.sort的原理，
再讲到如何对自定义类进行排序，
最后会介绍利用collections sort对自定义对象进行排序的另外一种方法，并将两种排序进行了简单的性能比较。
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中只有一个方法
java代码
public int compareto(t o);
也就是说实际上binarysort方法中调用的是comparable的compareto方法，以此可知只要继承自comparable，
并实现compareto即可调用collections.sort对自定义对象进行排序
2.3 自定义类的比较
下面代码为对user进行排序，首先按姓名字母先后排序，若姓名相同，则按年龄由小到大排序
java代码
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代码：
herry 19 herry 20 jack 19 james 18 james 19 jim 19 luccy 19 lucy 19
可以看出只需两点即可
a、继承自comparable
java代码
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代码
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代码
collections.sort(userlist, new comparator<user>())
为比较的主体，并且实现了comparator的compare方法。下面介绍下此种方法的原理
追踪collections的
java代码
public static <t> void sort(list<t> list, comparator<? super t> c)
到
java代码
public static <t> void sort(t[] a, comparator<? super t> c)
到
java代码
private static void mergesort(object[] src, object[] dest, int low, int high, int off, comparator c)
可以发现其中代码如下：
java代码
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排序原理就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持。