TreeMap 的排序及比较器问题

TreeMap 默认按键的自然顺序升序进行排序，如果有需求要按键的倒序排序，或者按值类型进行排序呢？
在问题开始之前，让我们先回顾一下有关 Map 及其排序基本的知识点

用的最多的 HashMap，不保证映射的顺序，特别是它不保证该顺序恒久不变。
LinkedHashMap,维持元素的插入顺序。
TreeMap 中有一个传入比较器的构造函数， Map 中的元素可按此比较器进行排序。

以上 3 个知识点，前 2 个作为复习，最后一个才是本次使用的重点。要想改变 TreeMap 的默认比较次序，我们可以在其构造函数中传入一个自己的比较器。TreeMap 的比较器构造函数如下：


  public TreeMap(Comparator<? super K> comparator)

Comaprator 排序接口定义如下：


public interface Comparator<T> {
   int compare(T o1, T o2);
   ....... //若干方法
}

Comparator 接口必须实现 compare()方法。返回的 int 值的正负表示两值的大小。本着先易后难原则，让我们先实现 TreeMap 按键倒序排序：


package top.wthfeng.hello;

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class Map2Test{
	public static void main(String[]args){
		Map<String,String> map = new TreeMap<>(new Comparator<String>(){
			public int compare(String o1,String o2){
				return  o2.compareTo(o1); //用正负表示大小值
			}
		});
		//以上4行可用下面一行lambda表达式代替
		//Map<String,String> map1 = new TreeMap<>((o1,o2)->o2.compareTo(o1));
		map.put("zdef","rfgh");
		map.put("asrg","zfg");
		map.put("rgd","dfgh");
		map.put("cbf","gddf");
		for(Map.Entry<String,String> entry:map.entrySet()){
			System.out.println("key:"+entry.getKey()+",:value:"+entry.getValue());			
		}
	}
}
//输出结果（倒序）：
key:zdef,:value:rfgh
key:rgd,:value:dfgh
key:cbf,:value:gddf
key:asrg,:value:zfg

在 TreeMap 的构造函数中传入实现了 Comparator 接口的类实例（本例以内部匿名类实现，道理都一样，匿名类更简单，当然 java8 以后更推荐使用 lambda 用法），该类的唯一方法 comparaTo()实现了比较算法。这样 TreeMap 的倒序排列就解决了。下面我们来研究 TreeMap 的按值排序。
先想想思路，map 的按值排序是没有现成方法的，这里就要变换一下想法。在集合工具类 Collections 中有对集合进行排序的方法，还可传入一个比较器按比较器进行排序。方法签名如下：


 public static <T> void sort(List<T> list,Comparator<? super T> c)；

这也就是说要是一个 list 的话，就像上面一样给传一个比较器，再调用 Collections.sort()方法就能解决，可这是 map 啊，那能不能将 map 转为 list 啊？直接看下面吧：


package top.wthfeng.hello;

import java.util.*;

public class MapTest{
	public static void main(String[]args){
		Map<String,String> map = new TreeMap<>();
		
		map.put("zdef","rfgh");
		map.put("asrg","zfg");
		map.put("rgd","dfgh");
		map.put("cbf","gddf");
		//将Map转为List
		List<Map.Entry<String,String>> list = new ArrayList<>(map.entrySet());
		Collections.sort(list, new Comparator<Map.Entry<String, String>>() {
			public int compare(Map.Entry<String, String> o1, Map.Entry<String, String> o2) {
				return  o2.getValue().compareTo(o1.getValue());
			}
		}); //重新排序
		//运用lambda表达式
		//Collections.sort(list,((o1, o2) -> o2.getValue().compareTo(o1.getValue())));
		for(Map.Entry<String,String> entry:list){
			System.out.println("key:"+entry.getKey()+",:value:"+entry.getValue());			
		}
	}
}
//输出（按值倒序）
key:asrg,:value:zfg
key:zdef,:value:rfgh
key:cbf,:value:gddf
key:rgd,:value:dfgh

OK,TreeMap 的按值排序就这样解决了。让我们总结一下，以上 2 个例子用到了 Comparator 这个接口，而这个接口到底是个怎样的存在呢？

强行对某个对象 collection 进行整体排序的比较函数。可以使用 Comparator 来控制某些数据结构（如有序 set 或有序映射）的顺序，或者为那些没有自然顺序的对象 collection 提供排序。

以上是 Java API6 上的说明，我又参考了其他资料，大致可以认为：是为那些没有排序方法的类自定义一个排序方法的一种手段，由于和原数据类没有耦合，又称之为外部比较器。比如说你写了一个苹果类，Apple 有 weight 属性。现要将 Apple 以 weight 升序放到 list 中，那么你就可以像上面那样，写个类实现 Comparator，在 Collections.sort()中实现排序。


package top.wthfeng.hello.test;

/**
 * 苹果类
 */
public class Apple {
    /**
     * 重量
     */
    private Integer weight;
    /**
     * 价格
     */
    private Integer price;

    public Integer getPrice() {
        return price;
    }

    public void setPrice(Integer price) {
        this.price = price;
    }

    public Integer getWeight() {
        return weight;
    }

    public void setWeight(Integer weight) {
        this.weight = weight;
    }

    @Override
    public String toString() {   //重写toString()方法，方面输出
         StringBuilder sb = new StringBuilder();
        sb.append("[");
        sb.append("Apple:(weight:");
        sb.append(weight);
        sb.append(",price:");
        sb.append(price);
        sb.append(")]");
        return sb.toString();
    }
}

package top.wthfeng.hello;

import top.wthfeng.hello.test.Apple;

import java.util.*;

public class Test {  //测试类
    public static void main(String[] args) {

        List<Apple> apples = new ArrayList<>();
        Random random = new Random(12);
        for (int i = 0; i < 10; i++) {  //生成10个苹果，重量随机生成
            Apple apple = new Apple();
            apple.setWeight(random.nextInt(1000));
            apples.add(apple);
        }
        for (Apple apple : apples) { //打印10个苹果的顺序
            System.out.println("apple = " + apple);
        }
        Collections.sort(apples, new Comparator<Apple>() { //排序，传入一个比较器
            @Override
            public int compare(Apple o1, Apple o2) {
                return o1.getWeight().compareTo(o2.getWeight());
            }
        });
        //  Collections.sort(apples,(o1,o2)->o1.getWeight().compareTo(o2.getWeight()));
        for (Apple apple : apples) { //排序后的顺序
            System.out.println(" sort apple = " + apple);
        }
    }
}
//输出
apple = [Apple:(weight:866,price:12)]
apple = [Apple:(weight:556,price:33)]
apple = [Apple:(weight:624,price:11)]
apple = [Apple:(weight:750,price:15)]
apple = [Apple:(weight:596,price:21)]
apple = [Apple:(weight:568,price:22)]
apple = [Apple:(weight:61,price:7)]
apple = [Apple:(weight:695,price:14)]
apple = [Apple:(weight:536,price:31)]
apple = [Apple:(weight:505,price:3)]
 sort apple = [Apple:(weight:61,price:7)]
 sort apple = [Apple:(weight:505,price:3)]
 sort apple = [Apple:(weight:536,price:31)]
 sort apple = [Apple:(weight:556,price:33)]
 sort apple = [Apple:(weight:568,price:22)]
 sort apple = [Apple:(weight:596,price:21)]
 sort apple = [Apple:(weight:624,price:11)]
 sort apple = [Apple:(weight:695,price:14)]
 sort apple = [Apple:(weight:750,price:15)]
 sort apple = [Apple:(weight:866,price:12)]

按 weight 排序完成。总结一下：我们自定义的类想按某个字段排序，可以利用 Collections 的 sort 方法传入一个自定义的比较器，这种比较器与被比较的类不发生耦合，称为外部比较器。
那么问题来了，如果我的 Apple 类默认排序是按价格，特殊情况才按重量。总不能每次排序时都要写遍比较器实现吧？这也太麻烦了。不知大家注意到没有，在实现 Comparator 接口中，都有类似下面的句子：

return o2.compareTo(o1);

那 compareTo()方法从哪来的？o1,o2 是 String 类型，compareTo()正是 String 实现的 Comparable 接口的方法。那么 Comparable 又是什么鬼？

Comparable 接口对实现它的每个类的对象进行整体排序，这种排序称为类的自然排序，类的 compareTo 方法被称为类的比较方法。

有点眉目了，再看看 Comparable 的解释，发现 java 中所有值类都实现了 Comparable 方法。像 String、Integer、Byte 等等。这些 java 内置的值类就是根据 compare 方法比较大小的，尤其重要的是，若类实现了 Comparable 接口，它就跟许多泛型算法及依赖于该接口的集合比较算法相关。这就是类的内部排序。


package top.wthfeng.hello.test;

/**
 * 苹果类
 */
public class Apple implements Comparable<Apple>{


    /**
     * 重量
     */
    private Integer weight;
    /**
     * 价格
     */
    private Integer price;

    public Integer getPrice() {
        return price;
    }

    public void setPrice(Integer price) {
        this.price = price;
    }

    public Integer getWeight() {
        return weight;
    }

    public void setWeight(Integer weight) {
        this.weight = weight;
    }

    @Override
    public String toString() {   //重写toString()方法，方面输出
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        sb.append("Apple:(weight:");
        sb.append(weight);
        sb.append(",price:");
        sb.append(price);
        sb.append(")]");
        return sb.toString();
    }

    @Override
    public int compareTo(Apple o) {  //实现内部排序
        return this.price.compareTo(o.getPrice());
    }
}

package top.wthfeng.hello;

import top.wthfeng.hello.test.Apple;

import java.util.*;

public class Test {
    public static void main(String[] args) {

        List<Apple> apples = new ArrayList<>();
        Random random = new Random(12);
        for (int i = 0; i < 10; i++) {  //生成10个苹果，重量随机生成
            Apple apple = new Apple();
            apple.setWeight(random.nextInt(1000));
            apple.setPrice(random.nextInt(50));
            apples.add(apple);
        }
        for (Apple apple : apples) { //打印10个苹果的顺序
            System.out.println("apple = " + apple);
        }
       Collections.sort(apples);
        //  Collections.sort(apples,(o1,o2)->o1.getWeight().compareTo(o2.getWeight()));
        for (Apple apple : apples) {
            System.out.println(" sort apple = " + apple);
        }
    }
}

//输出
apple = [Apple:(weight:866,price:12)]
apple = [Apple:(weight:556,price:33)]
apple = [Apple:(weight:624,price:11)]
apple = [Apple:(weight:750,price:15)]
apple = [Apple:(weight:596,price:21)]
apple = [Apple:(weight:568,price:22)]
apple = [Apple:(weight:61,price:7)]
apple = [Apple:(weight:695,price:14)]
apple = [Apple:(weight:536,price:31)]
apple = [Apple:(weight:505,price:3)]
 sort apple = [Apple:(weight:505,price:3)]
 sort apple = [Apple:(weight:61,price:7)]
 sort apple = [Apple:(weight:624,price:11)]
 sort apple = [Apple:(weight:866,price:12)]
 sort apple = [Apple:(weight:695,price:14)]
 sort apple = [Apple:(weight:750,price:15)]
 sort apple = [Apple:(weight:596,price:21)]
 sort apple = [Apple:(weight:568,price:22)]
 sort apple = [Apple:(weight:536,price:31)]
 sort apple = [Apple:(weight:556,price:33)]

根据指定属性和排序规则为数组进行排序

2020-08-17 描述将数组对象根据指定的属性和排序方式进行排序。提示使用 Array.prototype.sort() 在给定的 props 数组上使用默认值为 0 的 Array.prototype.reduce() 方法根据传如的排序规则使用数组解构来交换其属性位置 orders 数组的默认值为 'a ..

排序优化：如何实现一个通用的、高性能的排序函数？

本文章是从极客时间抄写的，仅仅是看不懂，抄了一遍，分享给大家。版权归极客邦科技所有几乎所有的编程语言都会提供排序函数，比如 C 语言中 qsort(),C++ STL 中的 sort()、stable_sort()，还有 Java 语言中的 Collections,sort()。在平时的开发中，我们也都是直接使用这 ..

排序（下）：如何用快排思想在 O(n) 内查找第 K 大元素？

本文章是从极客时间抄写的，仅仅是看不懂，抄了一遍，分享给大家。版权归极客邦科技所有上一节我讲了冒泡排序、插入排序、选择排序这三种排序算法，它们的时间复杂度都是 O(n2)，比较高，适合小规模数据的排序。今天，我讲两种时间复杂度为 O(nlogn)的排序算法，归并排序和快速排序。这两种排序算法适合大规模的数据排序，比 ..

排序（上）：为什么插入排序比冒泡排序更受欢迎？

本文章是从极客时间抄写的，仅仅是看不懂，抄了一遍，分享给大家。版权归极客邦科技所有排序对于任何一个程序员来说，可能都不会陌生。你学的第一个算法，可能就是排序。大部分编程语言中，也都提供了排序函数。在平常的项目中，我们也经常会用到排序。排序非常重要，所以我会花多一点时间来详细讲一讲经典的排序算法。排序算法太多了，有 ..

回顾快速排序算法

快速排序（Quicksort）是对[链接]的一种改进。快速排序由 C. A. R. Hoare 在 1962 年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以[链接]进行，以此达到整 ..

日常算法——希尔排序

希尔排序希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因 DL．Shell 于 1959 年提出而得名。该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行 ..

日常算法——简单选择排序

简单选择排序比如在一个长度为 N 的无序数组中，在第一趟遍历 N 个数据，找出其中最小的数值与第一个元素交换，第二趟遍历剩下的 N-1 个数据，找出其中最小的数值与第二个元素交换......第 N-1 趟遍历剩下的 2 个数据，找出其中最小的数值与第 N-1 个元素交换，至此选择排序完成。如图所示: [图片] 代码 ..

欢迎来到这里！

我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。

关于

TreeMap 的排序及比较器问题

相关帖子

根据指定属性和排序规则为数组进行排序

排序优化：如何实现一个通用的、高性能的排序函数？

排序（下）：如何用快排思想在 O(n) 内查找第 K 大元素？

排序（上）：为什么插入排序比冒泡排序更受欢迎？

回顾快速排序算法

日常算法——希尔排序

日常算法——简单选择排序

欢迎来到这里！

近期热议

推荐标签标签

最新标签

TreeMap 的排序及比较器问题

相关帖子

根据指定属性和排序规则为数组进行排序

排序优化：如何实现一个通用的、高性能的排序函数？

排序（下）：如何用快排思想在 O(n) 内查找第 K 大元素？

排序（上）：为什么插入排序比冒泡排序更受欢迎？

回顾快速排序算法

日常算法——希尔排序

日常算法——简单选择排序

欢迎来到这里！

近期热议

推荐标签 标签

最新标签

推荐标签标签