欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

5.4 集合的排序(Java学习笔记)(Collections.sort(),及Arrays.sort()底层分析)

程序员文章站 2022-09-22 08:12:23
1.Comparable接口 这个接口顾名思义就是用于排序的,如果要对某些对象进行排序,那么该对象所在的类必须实现 Comparabld接口。Comparable接口只有一个方法CompareTo(),这个方法可以看做是指定的排序规则。 内置类已经实现了CompareTo方法,例如long 小于返回 ......

1.comparable接口

这个接口顾名思义就是用于排序的,如果要对某些对象进行排序,那么该对象所在的类必须实现

comparabld接口。comparable接口只有一个方法compareto(),这个方法可以看做是指定的排序规则。

 

内置类已经实现了compareto方法,例如long

5.4 集合的排序(Java学习笔记)(Collections.sort(),及Arrays.sort()底层分析)

小于返回-1,等于返回0,大于返回1.

这里只举一个例子,例如int,double,date等可以排序的内置类都已经实现了compareto方法,即指定了排序规则。

 

2.collections.sort()和arrays.sort()方法。

colections是对集合进行操作的工具类,collection.sort是对集合排序的方法。

collections.sort()的底层实质是是调用arrays.sort();

我们来看下collections.sort()的源码:

5.4 集合的排序(Java学习笔记)(Collections.sort(),及Arrays.sort()底层分析)

首先传递进去的集合必须是comparable接口及其子类,而且后续会用到comparable接口中的compareto方法。所以进行排序的类必须实现comparable,

可以看出如果没有实现comparable接口,参数传递会出现错误。

我们点进list.sort()方法,就会看到下面代码:

5.4 集合的排序(Java学习笔记)(Collections.sort(),及Arrays.sort()底层分析)

我们可以看到,它是先将集合转换成数组,然后调用arrays.sort()方法。

排序排完后又将数组中元素逐个放入集合。

 

我们接下点进arrays.sort()方法的源码:

5.4 集合的排序(Java学习笔记)(Collections.sort(),及Arrays.sort()底层分析)

参数有两个,有一个之前转换成数组的集合a,c是一种排序规则,后面会讲到。没有指定话,会自动设置为null。

然后判断是否有排序规则,有就调用使用排序规则的排序方法。这里看出当设置了排序规则c时,会进入使用排序规则的比较方法进行比较,

此时compareto()是不起作用的,起作用的是排序规则c中实现的compare()方法。

接着进去sort().

5.4 集合的排序(Java学习笔记)(Collections.sort(),及Arrays.sort()底层分析)

我们可以看到这里有两个排序算法,使用legacymergesort.userrequested控制,第一个是归并排序,也就是legacymergesort.userrequested为true时进入的语句,

注意默认状态下legcymergesort是false,所以默认进去的是comparabletimsort.sort()。这时一种优化的排序算法,有兴趣可以去查询下,当然这种算法比较复杂,

不便于理解。legactmergesort()便于理解些,我们就先分析这个排序算法。

默认是进入comparabletimsort(),要想进入legacymergesort()我们就需要设置下legacymergesort.userrequested的值。

这时我们可以自己设置legacymergesort.userrequested的值,这句话是加在main中sort调用之前的。

system.setproperty("java.util.arrays.uselegacymergesort", "true");

设置为true后我们进入的就是legcymergesort();

/*
注意:
这里只是对排序算法的一种优化,排序时的规则是不变的的。
(例如我现在要进行升序排序,可以用很多算法,但是最后的结果一定是升序的。)
这里我们主要看compareto()方法返回值(1,0,-1)在排序中起到的作用,不关心具体算法的优化,有兴趣的可以自行查阅相关算法。
*/

 

那么我们这时就会进入gacymergesort();

我们点击该方法,看它的代码:

5.4 集合的排序(Java学习笔记)(Collections.sort(),及Arrays.sort()底层分析)

首先将存放集合数组的数组克隆,然后将克隆后的数组作为参数传递进aux,这里c为null进入第一个mergesort();

进入mergesort()我们可以看到:

5.4 集合的排序(Java学习笔记)(Collections.sort(),及Arrays.sort()底层分析)

我们先看传递进去的参数,srt,dest都是存放数据的数组,str是克隆的数组,dest是原数组,low=0,high=数组长度,off = 0;

首先定义了一个legth = high - low,得到的其实也是数组长度,

一开始进行一个判断,长度小于insertionsort_threshold(常量7)就采用更适合长度小于7的数组的插入排序算法,

我们可以看到代码中排序的依据是compareto()的返回值,如果返回值大于0则交换位置,反之则不交换。

如果不小于则采用适合数组长度大于7的其他排序方法。

后面还有更适合数组长度大于7的算法,这里没有贴出这部分代码,有兴趣可自己去了解下。

(这里只是对排序算法执行次数的一种优化,排序时的规则是不变的的。我们这里主要看compareto方法起到作用,不关心排序算法的优化。)

 

这里我们举一个简单的例子,假设现在我在链表里面存放了三个long型数据312;

我们从调用collections.sort()方法开始分析源码执行的过程,理解compareto方法的作用。

 进入mergesort()方法后,我们先来看下传递进来的参数:

dest[] = {3,1,2}, low = 0, high = 3(数组长度);

 

接下来分析代码执行过程:

首先i=0,然后j = 0,不满足条件直接跳出,然后i++

此时i = 1,j=1,此时将元素转换为comparable接口调用compareto方法根据之前看的long里面的compare方法(comparable)dest[0].compareto(dest[1]) = 1.

如果没有实现comparable接口,这里转型也会出现错误。

//调用comparto()返回值不清楚的,回到前面去看long里面compareto方法

交换dest[0],dest[1]位置,此时数组顺序:132.,然后j--,不满足循环条件直接跳出,执行i++。

此时i=2,j=2,(comparable)dest[1].compareto(dest[2]) = 1,交换dest[1],dest[2],此时数组顺序:123.执行i++;

i=3,不满足循环条件,退出执行retun,结束排序,最终数组顺序:123;

大家可以自己结合compareto方法的返回值分析分析排序过程。

 

了解了compareto在排序中起到的作用后,平常我们在实现comparable接口,

实现其中的compareto方法时我们就可以明确compareto的返回值。

例如,a<b return 1.再结合compareto方法为1则交换位置,此时就是降序排列,

如果是a>b return 1,就变成升序。分析源码后我们可以自己分析排序到是升序还是降序。

我们也可以这样理解,如果返回1就代表交换这两个元素位置。

 

//一般情况下大于返回1,等于返回0,小于返回-1,更符合我们的思维习惯,这时排序是升序

建议一般情况下这样写,此时是升序,如果是要求降序排列,改变返回值,将a>b return -1就是降序了。

 

再次声明,要使用排序方法,必须实现comparable接口。

 

我们来举一个具体的例子。例如新闻,我们首先要看时间降序(即最近发生的新闻出现在最前面),

其次按点击量降序(即点击量多的出现在前面)。

那么我们结合compareto方法在排序时的作用来考虑时间和点击量比较的返回值。

首先,最近发生的新闻排在前面,如果a新闻时间在b新闻时间后面(也就是a新闻发生的时间离我们最近),

越在后面的时间的数值越大,date本质上也是一个long型数。那么最近发生的排在前面应该降序。也就是if(a时间> b时间)return -1;

对date这一块理解有问题的,可参考

如果时间相同,我们再来考虑点击量,点击量大的排在前面。

那么这也是一个降序,if(点击量a > 点击量b) return -1;

这里也可以用之前如果返回1,就代表交换位置,-1就不交换位置这样来理解,理解的方式有很多种,

但归根结底都是对源码执行过程的分析,把握这一点就可以以不变应万变。

 

接下来我们来看具体的代码。

news类代码

import java.text.dateformat;
import java.text.simpledateformat;
import java.util.date;

public class news implements comparable<news>{
    private string newsname;
    private date date;
    private int click;
    private string times;
    public news(){}
    public news(string newsname, date date, int click){
        setnewsname(newsname);
        setdate(date);
        setclick(click);
    }
    public string getnewsname() {
        return newsname;
    }
    public void setnewsname(string newsname) {
        this.newsname = newsname;
    }
    public date getdate() {
        return date;
    }
    public void setdate(date date) {
        this.date = date;
        dateformat china_time = new simpledateformat("yyyy-mm-dd hh-mm-ss");
       times = china_time.format(date);
       
    }
    public int getclick() {
        return click;
    }
    public void setclick(int click) {
        this.click = click;
    }
    public int compareto(news o) {
        // todo auto-generated method stub
        if(this.getdate().after(o.getdate()))//这句话就是如果this.getdate()的值 > o.getdate(),就降序排列。
            return -1;                       //也可以理解为如果this.getdate()的值 >o.getdate(),则不交换位置,即降序。
        if(this.getclick() > o.click)//如果this的点击数大于o的点击数则降序排列,即点击量大的排在前面
            return -1;               //如果this的点击量大于o的点击量,则不交换位置,即降序排列
        return 1;
    }
       
    public string tostring(){
        return "标题:" + this.newsname + "时间" + times
        + "点击量" + this.click + "\n";
    }
}

 

运行代码

import java.util.arraylist;
import java.util.arrays;
import java.util.collections;
import java.util.comparator;
import java.util.date;
import java.util.linkedlist;
import java.util.list;
public class testcompare {
    public static void main(string[] args) {
        list<news> newslist = new linkedlist<>();
        newslist.add(new news("国庆高峰堵车,各景点爆满!",new date(),1000));//设置为当前时间
        newslist.add(new news("国庆仍有大部分家里蹲!",new date(system.currenttimemillis()-60*60*1000),100));//设置为当前时间前一小时
        newslist.add(new news("惊呆,游客竟在做这种事!!!",new date(),10000));//设置为当前时间,点击量10000
        system.setproperty("java.util.arrays.uselegacymergesort", "true");//设置为true进入legacysort() 
        system.out.println(newslist);
        collections.sort(newslist);
        system.out.println(newslist);
    }
}
运行结果:
//排序前新闻
[标题:国庆高峰堵车,各景点爆满!时间2018-10-07 09-23-53点击量1000
, 标题:国庆仍有大部分家里蹲!时间2018-10-07 08-23-54点击量100
, 标题:惊呆,游客竟在做这种事!!!时间2018-10-07 09-23-54点击量10000
]

//排序后新闻
[标题:惊呆,游客竟在做这种事!!!时间2018-10-07 09-23-54点击量10000
, 标题:国庆高峰堵车,各景点爆满!时间2018-10-07 09-23-53点击量1000
, 标题:国庆仍有大部分家里蹲!时间2018-10-07 08-23-54点击量100
]

我们可以看到,首先按时间(距离我们最近发生的新闻排在最前面)进行排序,时间相同按点击量排序。

 

我们可以看出mergesort中使用compareto方法只是判断是否大于0,

当我们的compareto()返回的是0或-1时,for()语句中判断都是false,那么我们能否在返回时不要-1,只返回0,1呢?

在当前方法(leacysort()中的mergesort())显然是可以的,因为0 > 0,-1>0的结果是相同的。

你要确定你进去的是leacysort()中的mergesort(),最好设置如下语句:

system.setproperty("java.util.arrays.uselegacymergesort", "true");

如果没有设置的话legcymergesort.userrequested默认为false,进去的就是另外一种排序算法,在另外一种算法中这样设置是不行的。

 

当默认为false时,我们进入另外一个算法看下:(这个算法只是简单点的过一遍,不分析具体步骤)

5.4 集合的排序(Java学习笔记)(Collections.sort(),及Arrays.sort()底层分析)

 为false时进去的是comparebletimsort.sort();我们进入这个算法看下:

5.4 集合的排序(Java学习笔记)(Collections.sort(),及Arrays.sort()底层分析)

首先一个断言,一般情况下都没有问题,

然后nremaing = hi - lo,hi是数组长度,lo是0.

min_merge是32。

接着就是根据数组a计算initrunlen的值,

我们先进入countrunandmakeascending();

5.4 集合的排序(Java学习笔记)(Collections.sort(),及Arrays.sort()底层分析)

但我们将-1也设置为0时,else后面的语句判断的是返回值>=0。-1和0去判断得到的结果是不同的。

这里会造成这个值有问题,而这个值需要传递到排序算法中,就会导致排序出现问题。news中的compareto方法的

返回值只有0,1的话这里的runhi - lo是3,如果是按照正常的1,0,-1来的话runhi - lo是2。这个可以结合源码自己分析一下。

这个执行完之后就要将得到的值,传入我们的排序算法中开始排序了。(上述分析都是基于之前代码中创建的三个新闻对象来分析的)

返回runhi-lo后,我们回到上一级

5.4 集合的排序(Java学习笔记)(Collections.sort(),及Arrays.sort()底层分析)

我们将值传入binarsort()中,然后点击binarysort:

5.4 集合的排序(Java学习笔记)(Collections.sort(),及Arrays.sort()底层分析)

5.4 集合的排序(Java学习笔记)(Collections.sort(),及Arrays.sort()底层分析)

5.4 集合的排序(Java学习笔记)(Collections.sort(),及Arrays.sort()底层分析)

这个具体过程就不一一分析了,有兴趣的可以分析下这些算法。

start就是之前的返回值(runhi - lo),如有只有1,0返回的是3,如果是正常的-1,0,1返回的是2.

我们来看第一个for语句,如果start是3就直接跳出循环(hi是数组长度,这里为3)不进行排序,原有数据不会发生变化。

如果是2,进行排序,最后输出是按照规则排序好的数据。

 

大家可以试下修改上面代码中nwes的compareto()方法的返回值和运行代码中设置true,false的部分:

(1)将 return -1改成return 0,legacymergesort.userrequested为false时,输出未正常排序结果。

                                                    legacymergesort.userrequested为true时,输出正常排序结果。

结合上述内容理解下整个的过程。

无论是哪种排序方法,严格按照(1,0,-1)返回,都可以输出对应逻辑排序结果。

结合例子、源码与上述内容分析分析,就可以清楚的知道排序执行的流程以及compareto()返回值的作用。

 

 

3.comparator接口

comparator和comparable类似,底层实现是一样的,理解了comparable中compareto()方法的作用后

理解comparator就很简单了。

 

我们之前说的实现comparable接口的compareto方法是写在需要进行排序的类里面的,可以说这种方法就从属于这个类。

但comparator就不一样了,它只是制定了一种排序规则,不需要从属于谁,谁需要用这个规则拿来用就可以了。

具体的操作是,新建一个规则类,例如我要按照新闻点击量排序,那么我可以把这个类命名为nwesclicksort

这个类需要实现comparator接口,并且实现里面的ompare()方法。 

 

我们来看下comparator接口中compare方法:

5.4 集合的排序(Java学习笔记)(Collections.sort(),及Arrays.sort()底层分析)

这个作用和compareto()方法的作用一样,也是比较两个值(o1,o2),然后返回1,0,-1.

使用compare排序时,就是调用这个方法来进行排序。

 

使用时,我们需要为newsclicksort这个类实例化一个对象,这个对象代表一种排序规则。

然后将集合和对象(排序规则)传递到collections.sort()中。

 

我们先来看个例子://这里面我们指定了一种排序规则,按照点击量来排序,nwes类还是之前的代码,没有任何修改。

import java.util.arraylist;
import java.util.arrays;
import java.util.collections;
import java.util.comparator;
import java.util.date;
import java.util.linkedlist;
import java.util.list;
public class testcompare {
    public static void main(string[] args) {
        list<news> newslist = new linkedlist<>();
        newslist.add(new news("国庆高峰堵车,各景点爆满!",new date(),1000));//设置为当前时间
        newslist.add(new news("国庆仍有大部分家里蹲!",new date(system.currenttimemillis()-60*60*1000),100));//设置为当前时间前一小时
        newslist.add(new news("惊呆,游客竟在做这种事!!!",new date(),10000));//设置为当前时间,点击量10000
        system.setproperty("java.util.arrays.uselegacymergesort", "true");//设置为true进入legacysort() 
        system.out.println(newslist);
        collections.sort(newslist,new newsclicksort());//传递进去的集合,和排序规则
        system.out.println(newslist);
    }
}
class newsclicksort implements comparator<news>{
   @override
   public int compare(news o1, news o2) {
     if(o1.getclick() < o2.getclick()){
        return 1;//这里写得不是很规范,最好是加上等于返回0,最后小于返回-1.
      }else{
        return -1;
      }
    }
}
运行结果:
//排序前结果 [标题:国庆高峰堵车,各景点爆满!时间2018-10-10 08-40-50点击量1000 , 标题:国庆仍有大部分家里蹲!时间2018-10-10 07-40-50点击量100 , 标题:惊呆,游客竟在做这种事!!!时间2018-10-10 08-40-50点击量10000 ] //排序后结果 [标题:惊呆,游客竟在做这种事!!!时间2018-10-10 08-40-50点击量10000 , 标题:国庆高峰堵车,各景点爆满!时间2018-10-10 08-40-50点击量1000 , 标题:国庆仍有大部分家里蹲!时间2018-10-10 07-40-50点击量100 ]

排序规则中只指定了点击量,所以排序后的结果是按点击量来排序的。

我们可以看到上面代码也设置了 

system.setproperty("java.util.arrays.uselegacymergesort", "true");//

 我们就来分析下使用comparator接口中的compare方法的执行过程。

第一步当然是点进main中的

collections.sort

5.4 集合的排序(Java学习笔记)(Collections.sort(),及Arrays.sort()底层分析)

注意那个c,就是实例化的比较规则。

我们继续点击sort():

5.4 集合的排序(Java学习笔记)(Collections.sort(),及Arrays.sort()底层分析)

我们会发现和之前看comparable接口排序的执行过程是一样的。

只是这时候c是实例化的排序规则,不是null了。

继续点击sort()

5.4 集合的排序(Java学习笔记)(Collections.sort(),及Arrays.sort()底层分析)

这时c不等于null,所以进入后面的if(legcymergesort.userrequested)进行判断

前面说了默认legaymergesort.userrequested是false,这里我们设置了为true,

所以我们点进legacymergesort():

5.4 集合的排序(Java学习笔记)(Collections.sort(),及Arrays.sort()底层分析)

c不等于null,我们点进第二个分支:

5.4 集合的排序(Java学习笔记)(Collections.sort(),及Arrays.sort()底层分析)

我们会发现和之前sort排序过程及compareto()的实现思路是一样的,只是一个调用的是compareto方法,

一个调用的是c.compare()方法。

 

legaymergesort.userrequested为false时,也和之前分析的sort排序过程及compareto()的实现思路是一样的,区别只是一个调用

的是compareto()方法,一个调用的是c.compare()方法。

legaymergesort.userrequested为false时的后续执行过程有兴趣可以去看下,会发现和前面讲的一样。

到这里整个比较过程就很清楚了。