This is my Blog!!Welcome to you!!
【分享个人java学习心得和技术问题汇总】

对象数组或list排序及Collections排序原理

常需要对list进行排序,小到List<String>,大到对自定义的类进行排序。不需要自行归并或堆排序。简单实现一个接口即可。

本文先会介绍利用Collections对List<String>进行排序,继而讲到Collections.sort的原理,

再讲到如何对自定义类进行排序,

最后会介绍利用Collections sort对自定义对象进行排序的另外一种方法,将两种排序进行了简单的性能比较。

下文中提到的如何追踪Collections等类的ava源代码,可以参考:http://trinea.iteye.com/blog/1351233

 

1、对List<String>排序及Collections.sort的原理

代码如下

 

其中Collections为java.util.Collections。

查看Collections中的sort实现

 

从中可以看出排序主体为Arrays.sort(array);Arrays的sort实现为


 

继续追踪,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中用于大小比较部分为

Java代码

 

会调用Object的compareTo进行比较。而默认类似String和Integer类型都已经覆盖compareTo方法。所以可以自行进行比较

 

2、对自定义类进行比较

通过上面的介绍了解了Collections排序的原理,下面介绍下自定义对象的排序,先查看下Integer和String的比较原理、然后介绍如何对自定义类进行比较

2.1 我们查看Object的实现发现其中并没有compareTo方法,

再看下Integer定义


 

再看下String的定义

 

我们可以发现他们都继承自Comparable

 

2.2 查看Comparable接口

可以发现Comparable中只有一个方法


 

也就是说实际上binarySort方法中调用的是Comparable的compareTo方法,以此可知只要继承自Comparable,

并实现compareTo即可调用Collections.sort对自定义对象进行排序

 

2.3 自定义类的比较

下面代码为对User进行排序,首先按姓名字母先后排序,若姓名相同,则按年龄由小到大排序

执行后输出为:

Xml代码
  1. Herry       19
  2. Herry       20
  3. Jack        19
  4. James       18
  5. James       19
  6. Jim     19
  7. Luccy       19
  8. Lucy        19

可以看出只需两点即可

a、继承自Comparable

 

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中的一样先比较姓名,若相等再比较年龄输出


 

 

可以看出其中


 

为比较的主体,并且实现了Comparator的compare方法。下面介绍下此种方法的原理

追踪Collections的


 

 

 

可以发现其中代码如下:


 

调用Comparator的compare方法

 

来源于:http://trinea.iteye.com/blog/1248517

未经允许不得转载:Java学习 » 对象数组或list排序及Collections排序原理

分享到:更多 ()