浅谈对象数组或list排序及Collections排序原理
常需要对list进行排序，小到List<String>，大到对自定义的类进行排序。不需要自行归并或堆排序。简单实现一个接口即可。
本文先会介绍利用Collections对List<String>进行排序，继而讲到Collections.sort的原理，
再讲到如何对自定义类进行排序，
最后会介绍利用Collectionssort对自定义对象进行排序的另外一种方法，并将两种排序进行了简单的性能比较。
1、对List<String>排序及Collections.sort的原理
代码如下
List<String>stringList=newArrayList<String>();
stringList.add("nice");
stringList.add("delicious");
stringList.add("able");
stringList.add("moon");
stringList.add("try");
stringList.add("friend");
Collections.sort(stringList);
for(Stringstr:stringList){
System.out.println(str);
}
其中Collections为java.util.Collections。
查看Collections中的sort实现
@SuppressWarnings("unchecked")
publicstatic<TextendsComparable<?superT>>voidsort(List<T>list){
Object[]array=list.toArray();
Arrays.sort(array);
inti=0;
ListIterator<T>it=list.listIterator();
while(it.hasNext()){
it.next();
it.set((T)array[i++]);
}
}
从中可以看出排序主体为Arrays.sort(array);Arrays的sort实现为
publicstaticvoidsort(Object[]array){
//BEGINandroid-changed
ComparableTimSort.sort(array);
//ENDandroid-changed
}
继续追踪，ComparableTimSort的sort实现ComparableTimSort.sort
staticvoidsort(Object[]a)到staticvoidsort(Object[]a,intlo,inthi)到privatestaticvoidbinarySort(Object[]a,intlo,inthi,intstart)。在binarySort中用于大小比较部分为
Comparable<Object>pivot=(Comparable)a[start];
intleft=lo;
intright=start;
assertleft<=right;
while(left<right){
intmid=(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定义
publicfinalclassIntegerextendsNumberimplementsComparable<Integer>
再看下String的定义
publicfinalclassStringimplementsjava.io.Serializable,Comparable<String>,CharSequence
我们可以发现他们都继承自Comparable
2.2查看Comparable接口
可以发现Comparable中只有一个方法
Java代码
publicintcompareTo(To);
也就是说实际上binarySort方法中调用的是Comparable的compareTo方法，以此可知只要继承自Comparable，
并实现compareTo即可调用Collections.sort对自定义对象进行排序
2.3自定义类的比较
下面代码为对User进行排序，首先按姓名字母先后排序，若姓名相同，则按年龄由小到大排序
Java代码
publicclassMainTest{
publicstaticvoidmain(String[]args){
List<User>userList=newArrayList<User>();
userList.add(newUser("Lucy",19));
userList.add(newUser("Jack",19));
userList.add(newUser("Jim",19));
userList.add(newUser("James",19));
userList.add(newUser("Herry",19));
userList.add(newUser("Luccy",19));
userList.add(newUser("James",18));
userList.add(newUser("Herry",20));
Collections.sort(userList);
for(Useruser:userList){
System.out.println(user.getName()+"\t\t"+user.getAge());
}
}
privatestaticclassUserimplementsComparable<User>{
privateStringname;
privateintage;
publicUser(Stringname,intage){
this.name=name;
this.age=age;
}
@Override
publicintcompareTo(Useranother){
intcompareName=this.name.compareTo(another.getName());
if(compareName==0){
return(this.age==another.getAge()?0:(this.age>another.getAge()?1:-1));
}
returncompareName;
}
publicStringgetName(){
returnname;
}
publicintgetAge(){
returnage;
}
}
}
执行后输出为：
Xml代码：
Herry19 Herry20 Jack19 James18 James19 Jim19 Luccy19 Lucy19
可以看出只需两点即可
a、继承自Comparable
Java代码
privatestaticclassUserimplementsComparable<User>
b、实现compareTo方法
上面的publicintcompareTo(Useranother)为比较的主体
可以看到其中intcompareName=this.name.compareTo(another.getName());表示比较姓名
若大于返回1，等于返回0，小于会返回-1。
若相等则按照intage的大小进行比较。
上面的
3、利用Collectionssort的重载函数对自定义对象进行排序
代码如下，仍同2中的一样先比较姓名，若相等再比较年龄输出
Java代码
publicclassMainTest{
publicstaticvoidmain(String[]args){
List<User>userList=newArrayList<User>();
userList.add(newUser("Lucy",19));
userList.add(newUser("Jack",19));
userList.add(newUser("Jim",19));
userList.add(newUser("James",19));
userList.add(newUser("Herry",19));
userList.add(newUser("Luccy",19));
userList.add(newUser("James",18));
userList.add(newUser("Herry",20));
Collections.sort(userList,newComparator<User>(){
publicintcompare(Useruser1,Useruser2){
intcompareName=user1.getName().compareTo(user2.getName());
if(compareName==0){
return(user1.getAge()==user2.getAge()?0:(user1.getAge()>user2.getAge()?1:-1));
}
returncompareName;
}
});
for(Useruser:userList){
System.out.println(user.getName()+"\t\t"+user.getAge());
}
}
privatestaticclassUser{
privateStringname;
privateintage;
publicUser(Stringname,intage){
this.name=name;
this.age=age;
}
publicStringgetName(){
returnname;
}
publicintgetAge(){
returnage;
}
}
}
可以看出其中
Java代码
Collections.sort(userList,newComparator<User>())
为比较的主体，并且实现了Comparator的compare方法。下面介绍下此种方法的原理
追踪Collections的
Java代码
publicstatic<T>voidsort(List<T>list,Comparator<?superT>c)
到
Java代码
publicstatic<T>voidsort(T[]a,Comparator<?superT>c)
到
Java代码
privatestaticvoidmergeSort(Object[]src,Object[]dest,intlow,inthigh,intoff,Comparatorc)
可以发现其中代码如下：
Java代码
if(length<INSERTIONSORT_THRESHOLD){
for(inti=low;i<high;i++)
for(intj=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排序原理就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持毛票票。