【语言热身】Java 中的排序

本文题目难度标识：🟩简单，🟨中等，🟥困难。

快速使用

现有以下数组或集合的定义：

public static void main(String[] args) {
	int[] nums = new int[]{3,2,5,7,1,9};
	List<Integer> ls = new ArrayList<Integer>(){{
		add(3);add(2);add(5);add(7);add(1);add(9);
	}};
	System.out.println("nums: "+Arrays.toString(nums));
	System.out.println("list: "+ls);
	// 输出
	// nums: [3, 2, 5, 7, 1, 9]
	// list: [3, 2, 5, 7, 1, 9]
}

排序方式	Arrays	Collections（以 ArrayList 举例）	顺序类型	注释
简单使用 sort 排序	Arrays.sort(nums);	Collections.sort(ls);	正序
sort 局部排序	Arrays.sort(nums,3,6);	-		左闭右开
reverse 逆序	-	Collections.reverse(ls);	逆序
使用现成的 Comparator：Collections.reverseOrder()	Arrays.sort(nums,Collections.reverseOrder());	Collections.sort(ls,Collections.reverseOrder()); ls.sort(Collections.reverseOrder());		数组要求是包装类型
通过 Lambda 提供自定义 Comparator（最简写法）	Arrays.sort(nums, (o1, o2) -> o2 - o1);	Collections.sort(ls,((o1, o2) -> o2-o1)); ls.sort(((o1, o2) -> o2 - o1));

注意到，在使用 Comparator 进行排序时，被排序的数组要求为装箱类型。除了使用循环一个个自动装箱以外，我们还可以使用 Arrays.stream 完成：

// int[] 转 Integer[]
int[] nums = new int[]{4,5,2,7,3,1,0,6,8,9};
Integer[] numsObject = Arrays.stream(nums).boxed().toArray(Integer[]::new);

// 使用 Comparator 进行排序
Arrays.sort(numsObject, (a,b)-> b-a); // 使用 Lambda 表达式实现倒序排序。

// Integer[] 转 int[]
int[] intArray = Arrays.stream(numsObject) // 转换为流
   .mapToInt(Integer::intValue) // 映射为基本类型 int
   .toArray(); // 收集为 int 数组

// 输出
System.out.println(Arrays.toString(intArray));

Character[] char[] 互转：

//Character[]转char[]
Character[] sc = {'d','a'};
Stream<Character> stream = Arrays.stream(sc);
String collect = stream.map(String::valueOf).collect(Collectors.joining());
char[] chars1 = collect.toCharArray();

//char[]转Character[]
char[] a = {'j','a'};
IntStream chars = String.valueOf(a).chars();
Stream<Character> characterStream1 = chars.mapToObj(b -> (char) b);
Character[] characters = characterStream1.toArray(Character[]::new);

本文的热身部分结束。下面内容需要花时间消化理解。

关于 Lambda 表达式的简化过程

Lambda 表达式是 Java 中典型的语法糖。

语法：

(Type parameter, ... ) ->{ statements; }

parameters 是参数列表， { statements; } 是 Lambda 表达式的主体。

简化写法：

• parameters 如果只有一个参数，可以省略括号；如果没有参数，也需要空括号。
• parameters 可以省略参数类型。
• statements; 只包含一条语句时，可省略大括号、分号
• -> 后可以紧接着一个普通的表达式：(int i,int j)->(i*j+2)

Lambda 表达式的作用之一是代替内部类。Lambda 表达式只能赋值给声明为函数式接口的 Java 类型的变量（注解 @FunctionalInterface）。Comparator 被标注为函数式接口，因此可以接受 Lambda 表达式。

这里以为 Arrays 写一个自定义 Comparator 实现逆序排序为例。一般的代码写法如下：

Comparator<Integer> myComparator = new Comparator<Integer>() {
	@Override
	public int compare(Integer o1, Integer o2) {
		return o2 - o1;
	}
};
Arrays.sort(nums, myComparator);

简化为（进而得到表格中的写法）：

Comparator<Integer> myComparator = (o1, o2) -> o2 - o1;
Arrays.sort(nums, myComparator);

分清楚 Comparable、Comparator、compare、compareTo?

字面含义的基本区分：

• Comparator「n. 比较器」。它以 -or 作为结尾，表示一个可执行某些动作的东西。它也是接口，它有多个待实现的方法，compare 是其中之一。
• Comparable 「adj. 可比的」。它以 -able 作为结尾，表示具备某种能力，一般用作 Java 接口。只有一个待实现的方法 compareTo。

@FunctionalInterface // 支持 Lambda
public interface Comparator<T> {
    int compare(T o1, T o2);
	/* 省略其他代码 */ 
}

public interface Comparable<T> {
    public int compareTo(T o);
}

compare 和 compareTo 的行为非常类似，都是返回一个整数值：

• 返回负数：当前对象小于传入对象
• 返回 0：当前对象和传入对象相等
• 返回正数：当前对象大于传入对象

区别在于：

• compare 需要传入两个参数表示两个对象。隐含地意思是，这种比较是一种「外部」的行为。
• compareTo 只需传入一个参数，表示传入对象。那么当前对象在哪呢，答案是在类里面，它是类内部定义的比较。

下面将通过自定义对象排序的例子说明这两种接口的使用异同。以及对「内部」「外部」的体会。

自定义对象的排序

现自定义对象 Person：

public static void main(String[] args) {
	class Person{
		String name;
		int score;
		public Person(String name,int score){
			this.name = name;
			this.score = score;
		}

		@Override
		public String toString(){
			return this.name + " " + this.score;
		}
	}
	Person[] team = new Person[]{
		new Person("学渣",40),
		new Person("学霸",100),
		new Person("普通人", 80),
	};
	System.out.println("排序前："+Arrays.toString(team));
	// 输出：
	// 排序前：[学渣 40, 学霸 100, 普通人 80]
}

现在我们需要将它们按成绩倒序排序。

使用 Comparator

在 main 函数中增加以下代码：

Comparator<Person> personComparator = new Comparator<Person>() {
	@Override
	public int compare(Person p1, Person p2) {
		return p2.score - p1.score;
	}
};
Arrays.sort(team,personComparator);
System.out.println("排序后："+Arrays.toString(team));

// 输出：
// 排序后：[学霸 100, 普通人 80, 学渣 40]

在以上示例中，我们没有动过 Person 类中的任何代码。我们是在外部自定义了一个 Comparator 对第三方类进行排序。也就是说通过 Comparator 接口可以实现和原有类的解耦，在不修改原有类的情况下实现排序功能，所以 Comparator 可以看作是「对外」提供排序的接口。

另外读者可以回忆一下上文提到的 Lambda，试着把代码优化一下。

阿里巴巴 Java 开发手册对集合使用的相关要求

一、（六）15.【强制】 在 JDK7 版本及以上， Comparator 实现类要满足如下三个条件， 不然 Arrays.sort，Collections.sort 会抛 IllegalArgumentException 异常。
说明： 三个条件如下
1） x， y 的比较结果和 y， x 的比较结果相反。
2） x > y， y > z， 则 x > z。
3） x = y， 则 x， z 比较结果和 y， z 比较结果相同。

使用 Comparable

使用 Comparable 接口时我们需要修改 Person 类的实现，使其具有「比较的能力」。

class Person implements Comparable<Person>{
	String name;
	int score;
	public Person(String name,int score){
		this.name = name;
		this.score = score;
	}

	@Override
	public String toString(){
		return this.name + " " + this.score;
	}

	@Override
	public int compareTo(Person p) {
		return p.score-this.score;
	}
}

使用方法：

Arrays.sort(team);
System.out.println("排序后："+Arrays.toString(team));
// 输出：
// 排序后：[学霸 100, 普通人 80, 学渣 40]

通过观察我们可以发现，使用 Comparable 接口我们需要「对内」修改类的实现，让类显式支持比较。且调用 sort 时不需要传入除了数组以外的其他参数。

需要注意的是，如果不向 sort 传入 Comparator，且数组内对象没实现 Comparable 的话会报错。

String 字符串的排序

在这个部分中，我们需要实现对 String 数组的逆序排序。代码涵盖 Comparable、Comparator、compare、compareTo，你能分清楚吗？

String[] names = {"Tom", "Jack", "Mike", "Linda", "Mary"};
System.out.println("排序前：" + Arrays.toString(names));

Arrays.sort(names);
System.out.println("正序排序：" + Arrays.toString(names));

Comparator<String> nameComparator = new Comparator<String>() {
	@Override
	public int compare(String s1, String s2) {
		return (s2.compareTo(s1));
	}
};
Arrays.sort(names, nameComparator);
System.out.println("逆序排序：" + Arrays.toString(names));

//    输出：
//    排序前：[Tom, Jack, Mike, Linda, Mary]
//    正序排序：[Jack, Linda, Mary, Mike, Tom]
//    逆序排序：[Tom, Mike, Mary, Linda, Jack]

附 String 类中 compareTo 的实现：

public int compareTo(String anotherString) {
	int len1 = value.length;
	int len2 = anotherString.value.length;
	int lim = Math.min(len1, len2);
	char v1[] = value;
	char v2[] = anotherString.value;

	int k = 0;
	while (k < lim) {
		char c1 = v1[k];
		char c2 = v2[k];
		if (c1 != c2) {
			return c1 - c2;
		}
		k++;
	}
	return len1 - len2;
}

二维向量排序

给定一堆向量，先按向量第一个参数排序，再按第二个参数进行排序。

int[][] nums2d = new int[][] {{2, 4}, {0, 2}, {0, 4}};
Arrays.sort(nums2d,(a,b) -> a[1] == b[1] ? a[0]-b[0] : a[1]-b[1]);
for(int[] e:nums2d){
	System.out.println(Arrays.toString(e));
}

// 输出：
// [0, 2]
// [0, 4]
// [2, 4]

在上面的例子中，二维数组为什么不需要转换为包装类型？

Java 中的数组是引用类型，被排序的数组 nums2d 是个二维数组，数组元素是一个个的一维数组（本质上是一个个 Object）。Comparator<int[]> 是符合 Java 语法要求的。

在 Lambda 写复杂函数时，最后一行记得显式 return（不管代码会不会到达），否则报错。

对 Map 和 Set 的排序

SortedSet 和 SortedMap 支持传入比较器实现自定义排序。在 SortedMap 中，我们自定义的是键的排序。

对普通的 Map，我们还可以将键值对输出到列表中，再对列表进行自定义排序。下面这个例子展示对 Map 的键值对先按值排序，再按键排序：

List<Map.Entry<Integer,Integer>> ls = new ArrayList<>(map.entrySet());
Collections.sort(ls,(e1,e2)->{
	int k1 = e1.getKey(),k2 = e2.getKey();
	int v1 = e1.getValue(), v2 = e2.getValue();
	return v1==v2 ? k1-k2:v1-v2;
});

相关题目

相信阅读到这里的你已经很熟练了。要不尝试下面的练习？

• 🟨 2545. 根据第 K 场考试的分数排序 - 力扣（LeetCode） 一行代码搞定。
• 🟨 791. 自定义字符串排序 - 力扣（LeetCode） 指定了字符串排序顺序，就是包装类转化有点复杂。
• 🟨 1387. 将整数按权重排序 - 力扣（LeetCode）
• 🟨 1366. 通过投票对团队排名 - 力扣（LeetCode）

本文参考

• Java Lambda 表达式 | 菜鸟教程 (runoob.com)
• 《Java 面向对象编程》孙卫琴 第 17 章
• Java 中使用 sort() 方法排序：从基本原理到多种用法全面总结；sort()函数的使用_java sort-CSDN博客
• Java 中初始化 List 集合的 6 种方式!_再list集合中初始化数据-CSDN博客
• 面试官：元素排序Comparable和Comparator有什么区别？-腾讯云开发者社区-腾讯云
• Character数组与char数组互转 - 简书