Java 对象排序完整版

2023-02-11 08:55:27

前几天在 LeetCode 刷题的时候,遇到了利用 Arrays.sort() 或 Collections.sort() 来对 Java 对象进行排序的需求,于是想较详细地总结一下 Java 对象的排序实现方法,这些方法能让我们的编程更快捷。

在 Java 中,基本使用两种方法,即 ComparatorComparable 接口,来完成基本甚至稍微复杂一点的排序的任务。当然,面对不同的数据结构,如数组(Array)、集合(Set)或映射(Map),排序的实现方式稍有不同。

要排序的对象

本文的任务就是对一系列的 Person 类对象进行排序,其中 Person 类的定义如下,

/** 原始 Person 类,每个对象包含 name 人名和 age 年龄属性 */
class Person {
    String name; // 人名
    int age; // 年龄
    public Person(String n, int a) {
        this.name = n;
        this.age = a;
    }
    /** 重写 Object 的 toString() 方法,便于打印对象 */
    @Override
    public String toString() {
        return ("name:" + this.name + ", age:" + this.age).toString();
    }
}

方法1: 使用 Comparable 接口

Comparble 接口的使用方法很直观,在要比较的对象的类的声明中实现 Comparable 接口即可。例如我们想要对 Person 对象进行排序,首先在 Person 类的声明中加上 implements Comparable<Person> 的语句,然后重写 Comparable 接口的 compareTo 的方法,按照比较规则返回 1,-1 或者 0。示例代码如下,

/** 实现了 Comparable 接口的 Person 类,
  * 每个 Person 对象都是可比较的,比较的依据是 age 属性。
  * */
class Person implements Comparable<Person>{
    String name; // 人名
    int age; // 年龄
    public Person(String n, int a){
        this.name = n;
        this.age = a;
    }
    /** 重写 Comparable 的 compareTo 方法,表示按照人的年龄来排序 */
    @Override
    public int compareTo(Person p2){
        if(this.age > p2.age){
            return 1;
        }else if(this.age < p2.age){
            return -1;
        }else{
            return 0;
        }
    }
    /** 重写 Object 的 toString() 方法,便于打印对象 */
    @Override
    public String toString(){
        return ("name:" + this.name + ", age:" + this.age).toString();
    }
}

在声明了上述的 Person 对象后,从根本上让 Person 对象具有了“可比较”的特性,我们直接利用 Arrays.sort() 或者 Collections.sort() 来比较一系列的 Person 对象了。示例代码如下,

import java.util.Arrays;

public class HelloWorld{
     public static void main(String []args){
        // 构建 Person 对象数组,包含 5 个对象
        Person[] ps = new Person[5];
        ps[0] = new Person("John", 30);
        ps[1] = new Person("Mike", 22);
        ps[2] = new Person("Kim", 34);
        ps[3] = new Person("Canddy", 25);
        ps[4] = new Person("Sam", 28);
        // 利用 sort 方法对 Person 数组进行排序
        Arrays.sort(ps);
        // 打印 Person 数组
        for(int i=0; i<ps.length; i++){
            System.out.println(ps[i]);
        }
    }
}

在这里插入图片描述
执行上述代码可以得到新的数组,我们打印这个数组,其输出确实是按照人的年龄排序的。而且 sort() 函数的排序效率较高,因此可以把排序数组放心的交给它。

这里插一句题外话,根据 Java 8 源码可知,Arrays.sort() 函数内部使用的排序算法是一种包含多种基本排序算法的混合算法1

在 Java 实现中,Arrays.sort()(主要针对数组)或 Collections.sort()(主要针对列表)底层使用了多种算法,大概的思路为,
  1 - 当元素个数小于 47 时,使用 插入排序算法(时间复杂度 O(n^2));
  2 - 当元素个数大于等于 47 且小于 286 时,使用 快速排序算法(时间复杂度 O(n × \times ×log(n)));
  3 - 当数组个数大于等于 286 时,使用 归并排序算法(时间复杂度O(n × \times ×log(n)),空间复杂度 O(n))。

方法 2:使用 Comparator 接口

上一节的比较对象的方式需要我们让对象类实现 Comparable 接口并重写 compareTo 方法,但当我们没有办法改变对象类的实现,只能靠外部来对对象进行排序时,就只能使用 Comparator 接口了。

在编程中,Comparator 接口一般被匿名继承并作为第二个参数传递给 Arrays.sort() 函数。按照上一节的例子,假设我们不能对 Person 类进行修改(使用原始的 Person 类),我们可以使用如下代码对其对象数组进行排序。

import java.util.Arrays;
import java.util.Comparator;

public class HelloWorld{
     public static void main(String []args){
        // 构建 Person 对象数组,包含 5 个对象
        Person[] ps = new Person[5];
        ps[0] = new Person("John", 30);
        ps[1] = new Person("Mike", 22);
        ps[2] = new Person("Kim", 34);
        ps[3] = new Person("Canddy", 25);
        ps[4] = new Person("Sam", 28);
        // 利用 sort 方法对 Person 数组进行排序
        Arrays.sort(ps, new Comparator<Person>(){
            /** 重写 compare 方法来对 Person 对象进行比较 */
            @Override
            public int compare(Person p1, Person p2){
                if(p1.age > p2.age){
                    return 1;
                }else if(p1.age < p2.age){
                    return -1;
                }else{
                    return 0;
                }
            }
        });
        // 打印 Person 数组
        for(int i=0; i<ps.length; i++){
            System.out.println(ps[i]);
        }
    }
}

在这里插入图片描述
可见比较的结果与使用 Comparable 接口的方法相同。

由于 Comparator 是函数式接口(只有一个抽象函数的接口),我们也可以使用 Lambda 表达式来让代码更简洁,此时只需要把核心代码改为,

// 利用 lambda 表达式来简化代码
Arrays.sort(ps, (Person p1, Person p2) -> {
	if(p1.age > p2.age) return 1;
	else if(p1.age < p2.age) return -1;
	else return 0;
});

这里插一句题外话,如果比较的是字符串,Java 提供了一个很好的比较方法,即 compareTo(String s),该方法能自动返回 2 个字符串大小比较的结果,比如说我们此处按照人名来排列,那么代码应该为,

Arrays.sort(ps, (Person p1, Person p2) -> {
	return p1.name.compareTo(p2.name);
});

Java 在实现 String 类(字符串类)的时候,为了方便字符串比较,也让 String 类实现了 comparable 接口,因此每个 String 对象均有 compareTo() 方法。该方法会从 2 个字符串首个字母开始,依次比较对应位置上的字符的 ASCII 码值,值越大的字符串更大2 。如 “aba”,“abb”,“abab” 的排序结果是 “aba”, “abab”, “abb”。

集合(Set)对象的排序

当 Person 对象出现在集合中时,如 HashSet 中时,我们是无法对集合中的元素进行排序的,这时候我们应该思考使用可替代的数据结构。这里给出使用 TreeSet 来对元素进行排序的实例,

import java.util.Set;
import java.util.TreeSet;
import java.util.Comparator;

public class HelloWorld{
     public static void main(String []args){
        // 构建 Person 对象集合,包含 5 个对象
        Set<Person> psSet = new TreeSet<Person>(new PersonComparator());
        psSet.add(new Person("John", 30));
        psSet.add(new Person("Mike", 22));
        psSet.add(new Person("Kim", 34));
        psSet.add(new Person("Canddy", 25));
        psSet.add(new Person("Sam", 28));
        // 打印 Person 数组
        for(int i=0; i<psList.size(); i++){
            System.out.println(psList.get(i));
        }
    }
}
/** Person 类的比较器 */
class PersonComparator implements Comparator<Person>{
	@Override
	public int compare(Person p1, Person p2) {
		if(p1.age > p2.age){
			return 1;
		}else if(p1.age < p2.age){
			return -1;
		}else {
			return 0;
		}
	}
}

TreeSet 的元素对象类继承 Compable 接口或提供一个继承 Comparator 的比较器。类似的,你也可以让 Person 类实现 Comparable 接口来让 TreeSet 中的元素变得有序。

映射(Map)对象的排序

Java 中的映射是一个 key-value 的键值对,我们既可以按照 key 排序,也可以按照 value 来排序。如果我们使用的是 TreeMap,那么该映射会自动按照 key 值进行排序;如果我们使用的是 HashMap,那么该映射的输出顺序是不定的。

但是无论针对哪一种映射结构,我们对其中的元素进行排序的方法都是固定的,也就是首先将映射中的所有 Entry 单元存放到一个 ArrayList 列表中去,然后对这个 ArrayList 进行排序。具体的实例代码如下,

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

public class HelloWorld{
	public static void main(String[] argv) {
		// 映射中初始有 5 个元素,key 为姓名,value 为年龄
		Map<String, Integer> psMap = new HashMap<String, Integer>();
		psMap.put("John", 30);
		psMap.put("Mike", 22);
		psMap.put("Kim", 34);
		psMap.put("Canddy", 25);
		psMap.put("Sam", 28);
		// 将映射中的 Entry 对象放入 ArrayList 中并排序
		List<Map.Entry<String, Integer>> list = new ArrayList<>(psMap.entrySet());
		Collections.sort(list, 
			(Map.Entry<String, Integer> e1, Map.Entry<String, Integer> e2) -> {
				if(e1.getValue() > e2.getValue()) return 1;
				else if(e1.getValue() < e2.getValue()) return -1;
				else return 0;
		});
		// 打印映射中的元素
		for(int i=0; i<list.size(); i++) {
			System.out.println(list.get(i).getKey() + ": " + list.get(i).getValue());
		}
	}
}

在 java 中,映射的底层实现是数组加链表(或红黑树)3,想要原地对映射进行排序是很困难的。因此,将映射中的 Entry 对象放入列表中排序只是一个权宜之计。另外,也建议大家使用 Entryset() 来遍历映射,因为它比使用键值来遍历(即 Keyset())更加高效。

小总

Java 对象的排序思路主要有 Comparable 和 Comparator 接口两种办法。前者让对象本身具有“可比较”的属性,即让对象类继承 Comparable 接口,重写 compareTo 方法;后者创建一个继承 Comparator 接口的比较器 XXCompartor,重写 compare 方法,最后将该比较器作为参数传递给 Arrays.sort() 或 Collection.sort() 方法。

针对不同数据结构中的对象,我们可以灵活设计排序方法。对于数组,我们使用 ArrayList.sort();对于列表,我们使用 Collections.sort();对于集合,我们使用 TreeSet 的数据结构;对于映射,我们针对每个 Entry 对象进行排序。

参考:


  1. Michael孟良, “剖析JDK8中Arrays.sort底层原理及其排序算法的选择”. Link ↩︎

  2. Kevin_cai09, “浅谈string中的compareTo方法”. Link ↩︎

  3. 清浅池塘, “HashMap底层实现原理”. Link ↩︎

  • 作者:chikily_yongfeng
  • 原文链接:https://blog.csdn.net/chikily_yongfeng/article/details/109898306
    更新时间:2023-02-11 08:55:27