Flueky 技术小站
浅谈 Java 中的排序
|Java

进来不要失望，这不是一篇讲排序算法的文章。而是简要介绍 Java 中排序相关的类Comparator、Comparable以及Collections.sort的使用。

写程序分为10个阶段：使用轮子、造轮子。程序猿也分10种：懂二进制的和不懂二进制的。调侃结束，着重介绍怎么造排序这个轮子。

1 认识Comparable和Comparator

Collections.sort可以给集合排序，前提是你需要制定一个排序规则。这就有了如下两种实现方式。

  • 使用Comparator给集合的item制定排序规则。
  • 使集合的item类型实现Comparable接口，自己实现排序规则。

1.1 认识Comparable

给类 T 实现Comparable接口，需要重写compareTo方法。return 正数表示不交换，return 负数时，交换this和 o两个对象。

1
2
3
4
@Override
public int compareTo(@NonNull Object o) {
    ……
}

然后就可以给 T 的集合进行排序：

1
Collections.sort(List<T> items);

1.2 认识Comparator

Comparable 只能给类 T 制定一种排序规则，文件管理器中，通常可以按照文件名称、类型、大小、创建（修改）时间给文件列表进行排序。只使用Comparable显然不能满足上述需求。此时需要使用Comparator给类 T 定义特定规则的排序器。

同样需要重写 compareTo方法,return 正数表示不交换，return 负数时，交换T1和 T2两个对象。

1
2
3
@Override
public int compare(T o1, T o2) {
}

给集合 T 进行排序：

1
Collections.sort(List<T> items,Comparator<T>);

1.3 例子

声明一个文件类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private static final class File {
    String name; //文件名称
    String type; //文件类型
    long size; //文件大小
    long createTime; //创建时间

    public File(String name, String type, long size, long createTime) {
        this.name = name;
        this.type = type;
        this.size = size;
        this.createTime = createTime;
    }

    @Override
    public String toString() {
        return name + " " + type + " " + size + " " + createTime;
    }
}

1.3.1 使用Comparable

File 实现 Comparable 接口：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
    * 定义升序排序规则
    * @param o
    * @return
    */
@Override
public int compareTo(@NonNull Object o) {
    if (!(o instanceof File))
        return 0;
    File f = (File) o;
    /**
     * 字符串，只能逐个比较字符，不使用 hashCode
     * 是因为 "b".hashCode()<"aa".hashCode()。升序排序时，"b"在"aa"前
     */
    char[] chars1 = this.name.toString().toCharArray();
    char[] chars2 = f.name.toString().toCharArray();
    for (int i = 0; i < chars1.length && i < chars2.length; i++) {
        if (chars1[i] == chars2[i])
            continue;
        return chars1[i] - chars2[i];
    }
    //如果执行到这里，表示前面比对的都相等，直到一方先结束或同时结束
    return chars1.length - chars2.length;
}

1.3.2 使用Comparator

给文件名定义排序器：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static final class FileNameComparator implements Comparator<File> {
    /**
        * 定义降序序排序规则
        * @param o1
        * @param o2
        * @return
        */
    @Override
    public int compare(File o1, File o2) {
        char[] chars1 = o1.name.toString().toCharArray();
        char[] chars2 = o2.name.toString().toCharArray();
        for (int i = 0; i < chars1.length && i < chars2.length; i++) {
            if (chars1[i] == chars2[i])
                continue;
            return chars2[i] - chars1[i];//注意这里同上面的不一样
        }
        //如果执行到这里，表示前面比对的都相等，直到一方先结束或同时结束
        return chars1.length - chars2.length;
    }
}

1.3.3 运行测试

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
public static final void main(String[] args) {
    List<File> files = new ArrayList<>();

    files.add(new File("qq", "exe", 10000, 242434234));
    files.add(new File("wxin", "exe", 10000, 24243424));
    files.add(new File("picture", "png", 100, 111111));
    files.add(new File("qqExter", "txt", 1000, 24243455));
    
    System.out.println("原始数据:");
    
    for (File f : files)
        System.out.println(f);

    System.out.println();
    System.out.println();

    System.out.println("使用Comparable给文件名升序排序:");
    Collections.sort(files);
    
    for (File f : files)
        System.out.println(f);

    System.out.println();
    System.out.println();

    System.out.println("使用Comparatore给文件名降序排序:");
    Collections.sort(files,new FileNameComparator());
    
    for (File f : files)
        System.out.println(f);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
原始数据:
qq exe 10000 242434234
wxin exe 10000 24243424
picture png 100 111111
qqExter txt 1000 24243455


使用Comparable给文件名升序排序:
picture png 100 111111
qq exe 10000 242434234
qqExter txt 1000 24243455
wxin exe 10000 24243424


使用Comparatore给文件名降序排序:
wxin exe 10000 24243424
qq exe 10000 242434234
qqExter txt 1000 24243455
picture png 100 111111

2 高级用法

这节的名字取得很响亮，是否高级请在最后给出合理评价。

2.1 对单个字段排序

之前提到过，要对文件名、文件类型、文件大小、创建（修改）时间进行排序。就是说要写四个排序器，每个排序器使用升序、降序再定义不同的排序规则。想想都很累。贴上代码，具体排序规则不一一实现了。

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
49
50
51
52
53
54
55
56
57
58
/**
    * 专用比较名称
    */
public static final class FileNameComparator implements Comparator<File> {

    /**
        * 定义降序排序规则
        * @param o1
        * @param o2
        * @return
        */
    @Override
    public int compare(File o1, File o2) {
        char[] chars1 = o1.name.toString().toCharArray();
        char[] chars2 = o2.name.toString().toCharArray();
        for (int i = 0; i < chars1.length && i < chars2.length; i++) {
            if (chars1[i] == chars2[i])
                continue;
            return chars2[i] - chars1[i];
        }
        //如果执行到这里，表示前面比对的都相等，直到一方先结束或同时结束
        return chars1.length - chars2.length;
    }
}

/**
    * 专用比较类型
    */
public static final class FileTypeComparator implements Comparator<File> {

    @Override
    public int compare(File o1, File o2) {

        return 0;
    }
}

/**
    * 专用比较创建时间
    */
public static final class FileCreateTimeComparator implements Comparator<File> {

    @Override
    public int compare(File o1, File o2) {
        return 0;
    }
}

/**
    * 专用比较文件大小
    */
public static final class FileSizeComparator implements Comparator<File> {

    @Override
    public int compare(File o1, File o2) {
        return 0;
    }
}

有兴趣的可以自己实现排序规则，但我相信见识了后面的高级用法，你也懒得写了。想说，复制代码是很低能的行为，复用代码才算入门的程序猿，否则就是从事体力劳作的码农。

对象比较，本质上是比较对象的各个属性，这些属性都应当是Java的基本数据类型。如果有基本数据类型之外的，如String，需要特殊处理。因此，我封装一个方法，专用比较基本数据类型和String。

2.1.1 介绍 hashCode

补充个基本常识，Java基本数据类型有：boolean、char、byte、short、int、long、double、float。好多人以为String也算，表示不理解。

下表列举出，基本数据类型的值和hash值之间的关系：

类型 值 hash值
byte 0xFF -1
short 128 128
int 65536 65536
long 1000000 1000000
boolean true 1231
char a 97
float 12.34f 1095069860
double 3.141592654 341533867

String值和hash值的关系：

值 hash值
“a” 97
“aa” 3104
“b” 98

基于上面的关系，封装下面的函数供使用：

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
/**
    * 对象比较，string对象比较字符，其余对象比较hash值
    *
    * @param value1
    * @param value2
    * @return
    */
private int compareValue(Object value1, Object value2) {
    if (value1 instanceof String) {
        /**
            * 字符串，只能逐个比较字符，不使用 hashCode
            * 是因为 "b".hashCode()<"aa".hashCode()。升序排序时，"b"在"aa"前
            */
        char[] chars1 = value1.toString().toCharArray();
        char[] chars2 = value2.toString().toCharArray();
        for (int i = 0; i < chars1.length && i < chars2.length; i++) {
            if (chars1[i] == chars2[i])
                continue;
            return chars1[i] - chars2[i];
        }
        //如果执行到这里，表示前面比对的都相等，直到一方先结束或同时结束
        return chars1.length - chars2.length;
    } else {
        return value1.hashCode() - value2.hashCode();
    }
}

不建议这里传入进本数据类型和String类型以外的类型，因为比较出来的结果可能出乎你意料。建议9个类型之外的类型比较，实现Comparable接口。

总不能，N个排序器 copy N次这个方法吧？别忘了咱的Java语言可是高级的面向对象编程语言。因此，抽象出一个通用的排序器：

2.1.2 抽象通用排序器

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
public abstract class CommonComparator<T> implements Comparator<T> {

    /**
     * 对象比较，string对象比较字符，其余对象比较hash值
     *
     * @param value1
     * @param value2
     * @return
     */
    protected int compareValue(Object value1, Object value2) {
        if (value1 instanceof String) {
            /**
             * 字符串，只能逐个比较字符，不使用 hashCode
             * 是因为 "b".hashCode()<"aa".hashCode()。升序排序时，"b"在"aa"前
             */
            char[] chars1 = value1.toString().toCharArray();
            char[] chars2 = value2.toString().toCharArray();
            for (int i = 0; i < chars1.length && i < chars2.length; i++) {
                if (chars1[i] == chars2[i])
                    continue;
                return chars1[i] - chars2[i];
            }
            //如果执行到这里，表示前面比对的都相等，直到一方先结束或同时结束
            return chars1.length - chars2.length;
        } else {
            return value1.hashCode() - value2.hashCode();
        }
    }
}

使用这个通用排序器：

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
49
50
/**
    * 专用比较名称
    */
public static final class FileNameComparator extends  CommonComparator<File> {

    /**
        * 定义降序排序规则
        *
        * @param o1
        * @param o2
        * @return
        */
    @Override
    public int compare(File o1, File o2) {
        return compareValue(o1.name, o2.name)*-1;//乘以-1 表示降序排序
    }
}

/**
    * 专用比较类型
    */
public static final class FileTypeComparator extends  CommonComparator<File> {

    @Override
    public int compare(File o1, File o2) {
        return compareValue(o1.type, o2.type);
    }
}

/**
    * 专用比较创建时间
    */
public static final class FileCreateTimeComparator extends  CommonComparator<File> {

    @Override
    public int compare(File o1, File o2) {
        return compareValue(o1.createTime, o2.createTime);
    }
}

/**
    * 专用比较文件大小
    */
public static final class FileSizeComparator extends  CommonComparator<File> {

    @Override
    public int compare(File o1, File o2) {
        return compareValue(o1.size, o2.size);
    }
}

同样这方法也能用在 Comparable 中：

1
2
3
4
5
6
7
8
9
10
11
12
/**
    * 根据文件名定义升序排序规则
    *
    * @param o
    * @return
    */
@Override
public int compareTo(@NonNull Object o) {
    if (!(o instanceof File))
        return 0;
    return compareValue(this.name, ((File) o).name);
}

如果认为封装 compareValue 方法，就是所谓的高级方法，那就大错特错。面向对象语言中的继承和复用是最近基本的使用方法。而且，目前只讲了对单个字段进行排序。

别忘了，程序猿最大的敌人不是设计出让你难以实现的效果的美工，也不是一直不断挑你毛病的测试，而是自己都不知道想要什么的产品经理。因此，建议对朝令夕改的产品经理要拿一把刀砍死。

2.2 对多个字段关联排序

有一天，产品经理突发奇想，要对文件类型进行排序的同时还要按照创建（修改）时间进行升序排序。人总不能真砍死，万一领导都认同了这个需求，那程序猿只有认命的份。

针对这个需求，在不改变之前代码的前提下，有两种实现方式：

  • 再使用个排序器，对文件类型和创建时间排序。
1
2
3
4
5
6
7
8
9
10
11
public static final class FileTypeAndCreateTimeComparator extends  CommonComparator<File> {

    @Override
    public int compare(File o1, File o2) {
        //先比较类型，类型一样再比较创建时间
        if(compareValue(o1.type, o2.type)==0)
            return compareValue(o1.createTime, o2.createTime);
        return compareValue(o1.type, o2.type);
    }
}

  • 先对文件类型排序，后对创建时间排序。
1
2
Collections.sort(files, new FileTypeComparator());
Collections.sort(files, new FileCreateTimeComparator());

如此轻快的实现这个需求，当你也忍不住想端起咖啡庆祝下时，产品经理又来了。90% 的情况下没好事。小伙子干的不错，我这还有个电商的项目。要对商品的人气、销量、价格进行排序，帮我实现下吧。既然拒绝不了，那就只能继续copy代码了。

所谓的高级用法此时体现在这里：怎样造一个轮子，既满足上面的需求，又能满足商品的排序。

未完待续。

觉得有用？那打赏一个呗。[去打赏](/donate/)

Author: flueky
Link: http://example.com/233/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.