对象排序
List l可以如下排序。
Collections.sort(l);
如果List包含String元素,它将按字母顺序排序,如果它由Date元素组成,它将按时间顺序排序,这是怎么发生的?String和Date都实现了Comparable接口,Comparable实现为类提供了自然的顺序,允许该类的对象自动排序,下表总结了一些实现Comparable的更重要的Java平台类。
类 | 自然排序 |
---|---|
Byte | 有符号数字 |
Character | 无符号数字 |
Long | 有符号数字 |
Integer | 有符号数字 |
Short | 有符号数字 |
Double | 有符号数字 |
Float | 有符号数字 |
BigInteger | 有符号数字 |
BigDecimal | 有符号数字 |
Boolean | Boolean.FALSE < Boolean.TRUE |
File | 依赖于系统的路径名称上的字典 |
String | 接字母顺序 |
Date | 按时间顺序 |
CollationKey | 特定于语言环境的字典 |
如果你尝试对列表进行排序,其中的元素未实现Comparable,Collections.sort(list)将抛出ClassCastException,类似地,如果你尝试使用comparator对其元素无法相互比较的列表进行排序,则Collections.sort(list, comparator)将抛出ClassCastException。虽然不同类型的元素可以相互比较,但这里列出的类别都不允许进行类间比较。
如果你只想对可比较元素的列表进行排序或创建它们的已排序集合,那么你真正需要了解Comparable接口的所有内容,如果要实现自己的Comparable类型,下一部分将是你感兴趣的。
编写自己的Comparable类型Comparable接口包含以下方法。
public interface Comparable{ public int compareTo(T o); }
compareTo方法将接收对象与指定对象进行比较,并返回负整数、0或正整数,具体取决于接收对象是否小于、等于或大于指定对象,如果无法将指定的对象与接收对象进行比较,则该方法将抛出ClassCastException。
以下表示人名的类实现了Comparable。
import java.util.*; public class Name implements Comparable{ private final String firstName, lastName; public Name(String firstName, String lastName) { if (firstName == null || lastName == null) throw new NullPointerException(); this.firstName = firstName; this.lastName = lastName; } public String firstName() { return firstName; } public String lastName() { return lastName; } public boolean equals(Object o) { if (!(o instanceof Name)) return false; Name n = (Name) o; return n.firstName.equals(firstName) && n.lastName.equals(lastName); } public int hashCode() { return 31*firstName.hashCode() + lastName.hashCode(); } public String toString() { return firstName + " " + lastName; } public int compareTo(Name n) { int lastCmp = lastName.compareTo(n.lastName); return (lastCmp != 0 ? lastCmp : firstName.compareTo(n.firstName)); } }
为了使前面的例子简短,该类有些限制:它不支持中间名,它要求名字和姓氏,并且它不以任何方式国际化,尽管如此,它还说明了以下要点:
Name对象是不可变的,在所有其他条件相同的情况下,不可变类型是解决问题的方法,特别是对于将作为集合中的元素或Map中的键使用的对象,如果你在集合中修改元素或键,这些集合将会中断。
构造函数检查其参数是否为null,这可以确保所有Name对象都格式正确,这样其他任何方法都不会抛出NullPointerException。
hashCode方法被重新定义,这对于重新定义equals方法的任何类都是必不可少的(等同对象必须具有相同的哈希码)。
如果指定的对象为null或类型不合适,则equals方法返回false,compareTo方法在这些情况下抛出运行时异常,这两种行为都是各自方法的一般契约所要求的。
toString方法已重新定义,因此它以人类可读的形式打印Name,这总是一个好主意,特别是对于要放入集合的对象,各种集合类型的toString方法依赖于其元素、键和值的toString方法。
由于本节是关于元素排序的,让我们再谈谈Name的compareTo方法,它实现了标准的名称排序算法,其中姓氏优先于名字,这正是你想要的自然顺序,如果自然顺序不自然,那将会非常混乱!
看看compareTo是如何实现的,因为它非常经典,首先,比较对象的最重要部分(在本例中为姓氏),通常,你可以只使用部分类型的自然顺序,在这种情况下,该部分是一个字符串,自然(词典)排序正是所要求的。如果比较的结果不是0(代表相等),那么就完成了:你只需返回结果。如果最重要的部分相同,则继续比较下一个最重要的部分,在这种情况下,只有两个部分 — 名字和姓氏。如果有更多的部分,你会以明显的方式进行,比较部分,直到你发现两个不相等或你正在比较最不重要的部分,此时你将返回比较的结果。
为了说明这一切都是有效的,这里有一个程序,它构建了一个名称列表并对它们进行排序。
import java.util.*; public class NameSort { public static void main(String[] args) { Name[] nameArray = { new Name("John", "Smith"), new Name("Karl", "Ng"), new Name("Jeff", "Smith"), new Name("Tom", "Rich") }; Listnames = Arrays.asList(nameArray); Collections.sort(names); System.out.println(names); } }
如果你运行这个程序,这是它打印的内容。
[Karl Ng, Tom Rich, Jeff Smith, John Smith]
compareTo方法的行为有四个限制,我们现在不会讨论它们,因为它们相当技术性和枯燥,最好留在API文档中,实现Comparable的所有类都遵守这些限制非常重要,因此如果你正在编写实现它的类,请阅读Comparable的文档。尝试对违反限制的对象列表进行排序具有未定义的行为,从技术上讲,这些限制确保自然顺序是实现它的类的对象的总顺序,这对于确保明确定义排序是必要的。
Comparators如果你想按一些对象的自然顺序以外的顺序排序,该怎么办?或者,如果要对某些未实现Comparable的对象进行排序,该怎么办?要执行上述任一操作,你需要提供Comparator — 一个封装排序的对象,与Comparable接口一样,Comparator接口由单个方法组成。
public interface Comparator{ int compare(T o1, T o2); }
compare方法比较它的两个参数,返回一个负整数、0或一个正整数,具体取决于第一个参数是小于、等于还是大于第二个参数,如果其中一个参数的Comparator类型不合适,则compare方法将抛出ClassCastException。
关于Comparable的大部分内容也适用于Comparator,编写compare方法与编写compareTo方法几乎完全相同,只是前者将两个对象作为参数传入,由于同样的原因,compare方法必须遵守与Comparable的compareTo方法相同的四个技术限制 — Comparator必须对它所比较的对象产生总顺序。
假设你有一个名为Employee的类,如下所示。
public class Employee implements Comparable{ public Name name() { ... } public int number() { ... } public Date hireDate() { ... } ... }
让我们假设Employee实例的自然顺序是员工姓名上的Name排序(如上例所定义),不幸的是,老板要求按照资历顺序列出员工名单。这意味着我们必须做一些工作,但并不多,以下程序将生成所需的列表。
import java.util.*; public class EmpSort { static final ComparatorSENIORITY_ORDER = new Comparator () { public int compare(Employee e1, Employee e2) { return e2.hireDate().compareTo(e1.hireDate()); } }; // Employee database static final Collection employees = ... ; public static void main(String[] args) { List e = new ArrayList (employees); Collections.sort(e, SENIORITY_ORDER); System.out.println(e); } }
程序中的Comparator相当简单,它依赖于应用于hireDate访问器方法返回的值的Date的自然顺序,注意,Comparator将第二个参数的雇用日期传递给第一个参数,而不是反过来,原因是最近招聘的员工级别最低,按雇用日期顺序排序会使该名单的资历顺序相反,人们有时用来达到这种效果的另一种技术是保持参数顺序,但要否定比较的结果。
// Don"t do this!! return -r1.hireDate().compareTo(r2.hireDate());
你应该总是使用前一种技术来支持后者,因为后者不能保证有效,这样做的原因是compareTo方法可以返回任何负整数,如果它的参数小于调用它的对象。有一个负整型数在被否定时仍然是负的,尽管这看起来很奇怪。
-Integer.MIN_VALUE == Integer.MIN_VALUE
上一个程序中的Comparator可以很好地对List进行排序,但确实存在一个缺陷:它不能用于排序已排序的集合,例如TreeSet,因为它生成的顺序与equals不兼容,这意味着这个Comparator相当于equals方法所没有的对象。特别是,在同一天雇佣的任何两名员工将相等,当你对List进行排序时,这并不重要,但是当你使用Comparator来排序一个已排序的集合时,它是致命的,如果你使用此Comparator将在同一日期雇用的多名员工插入到TreeSet中,则只会将第一个员工添加到该集合中,第二个将被视为重复元素,将被忽略。
要解决此问题,只需调整Comparator,以便生成与equals兼容的排序,换句话说,调整它以便在使用compare时看到相同的唯一元素是那些在使用equals进行比较时也被视为相等的元素。执行此操作的方法是执行两部分比较(像对于Name),其中第一部分是我们感兴趣的部分 — 在这种情况下,是雇用日期 — 第二部分是唯一标识对象的属性,员工编号在这里是明显的属性,这是比较器的结果。
static final ComparatorSENIORITY_ORDER = new Comparator () { public int compare(Employee e1, Employee e2) { int dateCmp = e2.hireDate().compareTo(e1.hireDate()); if (dateCmp != 0) return dateCmp; return (e1.number() < e2.number() ? -1 : (e1.number() == e2.number() ? 0 : 1)); } };
最后一点:你可能想要使用更简单的方法替换Comparator中的最终return语句:
return e1.number() - e2.number();
除非你绝对确定没有人会有负的员工编号,否则不要这样做!这个技巧通常不起作用,因为带符号整数类型不够大,不能表示两个任意带符号整数的差,如果i是一个大的正整数且j是一个大的负整数,i - j将溢出并返回一个负整数,由此产生的comparator违反了我们一直在讨论的四个技术限制之一(传递性)并产生可怕的、微妙的错误,这不是纯粹的理论问题。
上一篇:Map接口 下一篇:SortedSet接口文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/73965.html
集合接口 核心集合接口封装了不同类型的集合,如下图所示,这些接口允许独立于其表示的细节来操纵集合,核心集合接口是Java集合框架的基础,如下图所示,核心集合接口形成层次结构。 showImg(https://segmentfault.com/img/bVbntJW?w=402&h=146); Set是一种特殊的Collection,SortedSet是一种特殊的Set,依此类推,另请注意,层次结构...
摘要:从行,可以看出字符串的存储结构是字符数组。如果不相等,则返回两字符的编码值的差值第行当前字符串和另一个字符串,依次字符比较。如果均相等,则返回两个字符串长度的差值所以要排序,肯定先有比较能力,即实现接口。摘要: 原创出处 https://www.bysocket.com 「公众号:泥瓦匠BYSocket 」欢迎关注和转载,保留摘要,谢谢!这是泥瓦匠的第103篇原创《程序兵法:Java Str...
Queue接口 Queue是在处理之前保存元素的集合,除了基本的Collection操作外,队列还提供额外的插入、删除和检查操作,Queue接口如下。 public interface Queue extends Collection { E element(); boolean offer(E e); E peek(); E poll(); E remov...
摘要:简明教程原文译者黄小非来源简明教程并没有没落,人们很快就会发现这一点欢迎阅读我编写的介绍。编译器会自动地选择合适的构造函数来匹配函数的签名,并选择正确的构造函数形式。 Java 8 简明教程 原文:Java 8 Tutorial 译者:ImportNew.com - 黄小非 来源:Java 8简明教程 Java并没有没落,人们很快就会发现这一点 欢迎阅读我编写的Java ...
默认方法 接口部分描述了一个涉及计算机控制汽车制造商的例子,他们发布了行业标准接口,描述了可以调用哪些方法来操作他们的汽车,如果那些计算机控制的汽车制造商为他们的汽车添加新的功能,如飞行,该怎么办?这些制造商需要指定新的方法,以使其他公司(如电子制导仪器制造商)能够使其软件适应飞行汽车,这些汽车制造商将在哪里声明这些与飞行有关的新方法?如果他们将它们添加到原始接口,那么实现了这些接口的程序员将不得...
阅读 1460·2021-11-22 14:44
阅读 2842·2021-11-16 11:44
阅读 3205·2021-10-13 09:40
阅读 1979·2021-10-08 10:04
阅读 2363·2021-09-24 10:28
阅读 2909·2021-09-06 15:02
阅读 2956·2019-08-30 15:52
阅读 2391·2019-08-30 13:20