Java:比较与排序

古城微笑少年丶 2022-01-11 05:59 191阅读 0赞

**1.****两种比较接口分析**

在“集合框架”中有两种比较接口：Comparable接口和Comparator接口。Comparable是通用的接口，用户可以实现它来完成自己特定的比较，而Comparator可以看成一种算法的实现，在需要容器集合实现比较功能的时候，来指定这个比较器，这可以看成一种设计模式，将算法和数据分离。

前者应该比较固定，和一个具体类相绑定，而后者比较灵活，它可以被用于各个需要比较功能的类使用。

一个类实现了Camparable接口表明这个类的对象之间是可以相互比较的。如果用数学语言描述的话就是这个类的对象组成的集合中存在一个全序。这样，这个类对象组成的集合就可以使用Sort方法排序了。

而Comparator的作用有两个：

1、如果类的设计师没有考虑到Compare的问题而没有实现Comparable接口，可以通过Comparator来实现比较算法进行排序；

2、为了使用不同的排序标准做准备，比如：升序、降序或其他什么序。

**2 Comparable****接口**

<table> 
 <tbody> 
 <tr> 
 <td style="width:426.1pt;"> public&nbsp;interface&nbsp;Comparable&lt;T&gt; { &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;int&nbsp;compareTo(T o); } </td> 
 </tr> 
 </tbody> 
</table>

java.lang. Comparable接口定义类的自然顺序，实现该接口的类就可以按这种方式排序。

1）int compareTo(Object o): 比较当前实例对象与对象o，如果位于对象o之前，返回负值，如果两个对象在排序中位置相同，则返回0，如果位于对象o后面，则返回正值。

2）在 Java 2 SDK版本1.4中有二十四个类实现Comparable接口。下表展示了8种基本类型的自然排序。虽然一些类共享同一种自然排序，但只有相互可比的类才能排序。

<table> 
 <tbody> 
 <tr> 
 <td style="width:340.667px;"> 类 </td> 
 <td style="width:415.333px;"> 排序 </td> 
 </tr> 
 <tr> 
 <td style="width:340.667px;"> BigDecimal,BigInteger,Byte,Double, Float,Integer,Long,Short </td> 
 <td style="width:415.333px;"> 按数字大小排序 </td> 
 </tr> 
 <tr> 
 <td style="width:340.667px;"> Character </td> 
 <td style="width:415.333px;"> 按&nbsp;Unicode&nbsp;值的数字大小排序 </td> 
 </tr> 
 <tr> 
 <td style="width:340.667px;"> String </td> 
 <td style="width:415.333px;"> 按字符串中字符&nbsp;Unicode&nbsp;值排序 </td> 
 </tr> 
 </tbody> 
</table>

利用Comparable接口创建自己的类的排序顺序，只是实现compareTo()方法的问题。通常就是依赖几个数据成员的自然排序。同时类也应该覆盖equals()和hashCode()以确保两个相等的对象返回同一个哈希码。

这个接口的作用：如果数组或者集合中的（类）元素实现了该接口的话,我们就可以调用Collections.sort和Arrays.sort排序，或应用于有序集合TreeSet和TreeMap中。

下面设计一个有序的类Person，它实现Comparable接口，以年龄为第一关键字，姓名为第二关键字升序排序。

Person.java

<table> 
 <tbody> 
 <tr> 
 <td style="width:426.1pt;"> package&nbsp;com.zj.sort.comparable; public&nbsp;class&nbsp;Person&nbsp;implements&nbsp;Comparable&lt;Person&gt; { &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;int&nbsp;age; &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;String&nbsp;name; &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;Person(int&nbsp;age, String name) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;this.age&nbsp;= age; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;this.name&nbsp;= name; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;int&nbsp;compareTo(Person person) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;cop =&nbsp;age&nbsp;- person.getAge(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(cop != 0) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;cop; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;name.compareTo(person.name); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;int&nbsp;getAge() { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;age; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;String getName() { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;name; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;int&nbsp;hashCode() { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;result = 17; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result = 37 * result +&nbsp;age; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result = 37 * result +&nbsp;name.hashCode(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;result; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;boolean&nbsp;equals(Object o) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(!(o&nbsp;instanceof&nbsp;Person)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;false; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Person person = (Person) o; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;(age&nbsp;== person.age) &amp;&amp; (name.equals(person.name)); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;String toString() { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;(age&nbsp;+&nbsp;"{"&nbsp;+&nbsp;name&nbsp;+&nbsp;"}"); &nbsp;&nbsp;&nbsp;&nbsp;} } </td> 
 </tr> 
 </tbody> 
</table>

2.1 测试Arrays.sort（）方法

ArraysSortUnit.java

结果：

\[20\{Tom\}, 20\{Jeff\}, 30\{Mary\}, 20\{Ada\}, 40\{Walton\}, 61\{Peter\}, 20\{Bush\}\]

\[20\{Ada\}, 20\{Bush\}, 20\{Jeff\}, 20\{Tom\}, 30\{Mary\}, 40\{Walton\}, 61\{Peter\}\]

2.2 测试Collections.sort（）方法

CollctionsSortUnit.java

结果：

\[20\{Tom\}, 20\{Jeff\}, 30\{Mary\}, 20\{Ada\}, 40\{Walton\}, 61\{Peter\}, 20\{Bush\}\]

\[20\{Ada\}, 20\{Bush\}, 20\{Jeff\}, 20\{Tom\}, 30\{Mary\}, 40\{Walton\}, 61\{Peter\}\]

2.3 测试TreeSet

TreeSetUnit.java

结果：

\[20\{Ada\}, 20\{Bush\}, 20\{Jeff\}, 20\{Tom\}, 30\{Mary\}, 40\{Walton\}, 61\{Peter\}\]

2.4 测试TreeMap

TreeMapUnit.java

结果：

\{20\{Ada\}=Ada, 20\{Bush\}=Bush, 20\{Jeff\}=Jeff, 20\{Tom\}=Tom, 30\{Mary\}=Mary, 40\{Walton\}=Walton, 61\{Peter\}=Peter\}

**3. Comparator****接口**

<table> 
 <tbody> 
 <tr> 
 <td style="width:426.1pt;"> public&nbsp;interface&nbsp;Comparator&lt;T&gt; { &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;compare(T o1, T o2); &nbsp;&nbsp;&nbsp;&nbsp;boolean&nbsp;equals(Object obj); } </td> 
 </tr> 
 </tbody> 
</table>

若一个类不能用于实现java.lang.Comparable，或者不喜欢缺省的Comparable行为并想提供自己的排序顺序(可能多种排序方式)，你可以实现Comparator接口，从而定义一个比较器。

1）int compare(Object o1, Object o2): 对两个对象o1和o2进行比较，如果o1位于o2的前面，则返回负值，如果在排序顺序中认为o1和o2是相同的，返回0，如果o1位于o2的后面，则返回正值。

2）与Comparable相似，0返回值不表示元素相等。一个0返回值只是表示两个对象排在同一位置。由Comparator用户决定如何处理。

3）boolean equals(Object obj): 指示对象obj是否和比较器相等。该方法覆写Object的equals()方法，检查的是Comparator实现的等同性，不是处于比较状态下的对象。你想提升自己吗？欢迎加入java技术交流659270626

下面设计一个定义完整equals方法和hashCode方法的类Person。

Person.java

<table> 
 <tbody> 
 <tr> 
 <td style="width:426.1pt;"> package&nbsp;com.zj.sort.comparator; public&nbsp;class&nbsp;Person { &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;String&nbsp;firstName; &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;String&nbsp;lastName; &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;int&nbsp;age; &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;Person(int&nbsp;age, String firstName, String lastName) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;this.age&nbsp;= age; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;this.firstName&nbsp;= firstName; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;this.lastName&nbsp;= lastName; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;int&nbsp;getAge() { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;age; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;String getFirstName() { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;firstName; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;String getLastName() { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;lastName; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;int&nbsp;hashCode() { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;result = 17; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result = 37 * result +&nbsp;age; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result = 37 * result +&nbsp;firstName.hashCode(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result = 37 * result +&nbsp;lastName.hashCode(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;result; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;boolean&nbsp;equals(Object o) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(!(o&nbsp;instanceof&nbsp;Person)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;false; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Person p = (Person) o; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;(age&nbsp;== p.age) &amp;&amp; (firstName.equals(p.firstName)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&amp;&amp; (lastName.equals(p.lastName)); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;String toString() { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;(age&nbsp;+&nbsp;"{"&nbsp;+&nbsp;firstName&nbsp;+&nbsp;" "&nbsp;+&nbsp;lastName&nbsp;+&nbsp;"}"); &nbsp;&nbsp;&nbsp;&nbsp;} } </td> 
 </tr> 
 </tbody> 
</table>

下面设计两个比较器。

FirstNameComparator.java

LastNameComparator.java

下面通过上述两个比较器，调用Collections.sort和Arrays.sort排序，以及将其应用于有序集合TreeSet和TreeMap中。

3.1 测试Arrays.sort（）方法

ArraysSortUnit.java

结果：

\[20\{Tom A\}, 20\{Jeff A\}, 30\{Mary A\}, 20\{Ada B\}, 40\{Walton B\}, 61\{Peter B\}, 20\{Bush B\}\]

\[20\{Ada B\}, 20\{Bush B\}, 20\{Jeff A\}, 30\{Mary A\}, 61\{Peter B\}, 20\{Tom A\}, 40\{Walton B\}\]

\[20\{Jeff A\}, 30\{Mary A\}, 20\{Tom A\}, 20\{Ada B\}, 20\{Bush B\}, 61\{Peter B\}, 40\{Walton B\}\]

3.2 测试Collections.sort（）方法

CollctionsSortUnit.java

结果：

\[20\{Tom A\}, 20\{Jeff A\}, 30\{Mary A\}, 20\{Ada B\}, 40\{Walton B\}, 61\{Peter B\}, 20\{Bush B\}\]

\[20\{Ada B\}, 20\{Bush B\}, 20\{Jeff A\}, 30\{Mary A\}, 61\{Peter B\}, 20\{Tom A\}, 40\{Walton B\}\]

\[20\{Jeff A\}, 30\{Mary A\}, 20\{Tom A\}, 20\{Ada B\}, 20\{Bush B\}, 61\{Peter B\}, 40\{Walton B\}\]

3.3 测试TreeSet

TreeSetUnit.java

结果：

\[20\{Ada B\}, 20\{Bush B\}, 20\{Jeff A\}, 30\{Mary A\}, 61\{Peter B\}, 20\{Tom A\}, 40\{Walton B\}\]

\[20\{Jeff A\}, 30\{Mary A\}, 20\{Tom A\}, 20\{Ada B\}, 20\{Bush B\}, 61\{Peter B\}, 40\{Walton B\}\]

3.4 测试TreeMap

TreeMapUnit.java

<table> 
 <tbody> 
 <tr> 
 <td style="width:426.1pt;"> package&nbsp;com.zj.sort.comparator; import&nbsp;java.util.TreeMap; public&nbsp;class&nbsp;TreeMapUnit { &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;static&nbsp;void&nbsp;main(String[] args) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;TreeMap&lt;Person, String&gt; firstNameMap =&nbsp;new&nbsp;TreeMap&lt;Person, String&gt;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new&nbsp;FirstNameComparator()); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;firstNameMap.put(new&nbsp;Person(20,&nbsp;"Tom",&nbsp;"A"),&nbsp;"Tom A"); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;firstNameMap.put(new&nbsp;Person(20,&nbsp;"Jeff",&nbsp;"A"),&nbsp;"Jeff A"); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;firstNameMap.put(new&nbsp;Person(30,&nbsp;"Mary",&nbsp;"A"),&nbsp;"Mary A"); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;firstNameMap.put(new&nbsp;Person(20,&nbsp;"Ada",&nbsp;"B"),&nbsp;"Ada B"); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;firstNameMap.put(new&nbsp;Person(40,&nbsp;"Walton",&nbsp;"B"),&nbsp;"Walton B"); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;firstNameMap.put(new&nbsp;Person(61,&nbsp;"Peter",&nbsp;"B"),&nbsp;"Peter B"); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;firstNameMap.put(new&nbsp;Person(20,&nbsp;"Bush",&nbsp;"B"),&nbsp;"Bush B"); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(firstNameMap); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;TreeMap&lt;Person, String&gt; lastNameMap =&nbsp;new&nbsp;TreeMap&lt;Person, String&gt;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new&nbsp;LastNameComparator()); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;lastNameMap.putAll(firstNameMap); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(lastNameMap); &nbsp;&nbsp;&nbsp;&nbsp;} } </td> 
 </tr> 
 </tbody> 
</table>

结果：

\{20\{Ada B\}=Ada B, 20\{Bush B\}=Bush B, 20\{Jeff A\}=Jeff A, 30\{Mary A\}=Mary A, 61\{Peter B\}=Peter B, 20\{Tom A\}=Tom A, 40\{Walton B\}=Walton B\}

\{20\{Jeff A\}=Jeff A, 30\{Mary A\}=Mary A, 20\{Tom A\}=Tom A, 20\{Ada B\}=Ada B, 20\{Bush B\}=Bush B, 61\{Peter B\}=Peter B, 40\{Walton B\}=Walton B\}