數組排序 · 《Java 編程思想》第五版

## 數組排序根據對象的實際類型執行比較排序。一種方法是為不同的類型編寫對應的排序方法，但是這樣的代碼不能復用。編程設計的一個主要目標是“將易變的元素與穩定的元素分開”，在這里，保持不變的代碼是一般的排序算法，但是變化的是對象的比較方式。因此，使用策略設計模式而不是將比較代碼放入許多不同的排序源碼中。使用策略模式時，變化的代碼部分被封裝在一個單獨的類(策略對象)中。您將一個策略對象交給相同的代碼，該代碼使用策略模式來實現其算法。通過這種方式，您將使用相同的排序代碼，使不同的對象表達不同的比較方式。 Java有兩種方式提供比較功能。第一種方法是通過實現 **java.lang.Comparable** 接口的原生方法。這是一個簡單的接口，只含有一個方法 **compareTo()**。該方法接受另一個與參數類型相同的對象作為參數，如果當前對象小于參數，則產生一個負值;如果參數相等，則產生零值;如果當前對象大于參數，則產生一個正值。這里有一個類，它實現了 **Comparable** 接口并演示了可比性，而且使用Java標準庫方法 **Arrays.sort()**: ```JAVA // arrays/CompType.java // Implementing Comparable in a class import onjava.*; import java.util.Arrays; import java.util.SplittableRandom; import static onjava.ArrayShow.*; public class CompType implements Comparable<CompType> { private static int count = 1; private static SplittableRandom r = new SplittableRandom(47); int i; int j; public CompType(int n1, int n2) { i = n1; j = n2; } public static CompType get() { return new CompType(r.nextInt(100), r.nextInt(100)); } public static void main(String[] args) { CompType[] a = new CompType[12]; Arrays.setAll(a, n -> get()); show("Before sorting", a); Arrays.sort(a); show("After sorting", a); } @Override public String toString() { String result = "[i = " + i + ", j = " + j + "]"; if (count++ % 3 == 0) result += "\n"; return result; } @Override public int compareTo(CompType rv) { return (i < rv.i ? -1 : (i == rv.i ? 0 : 1)); } } /* Output: Before sorting: [[i = 35, j = 37], [i = 41, j = 20], [i = 77, j = 79] , [i = 56, j = 68], [i = 48, j = 93], [i = 70, j = 7] , [i = 0, j = 25], [i = 62, j = 34], [i = 50, j = 82] , [i = 31, j = 67], [i = 66, j = 54], [i = 21, j = 6] ] After sorting: [[i = 0, j = 25], [i = 21, j = 6], [i = 31, j = 67] , [i = 35, j = 37], [i = 41, j = 20], [i = 48, j = 93] , [i = 50, j = 82], [i = 56, j = 68], [i = 62, j = 34] , [i = 66, j = 54], [i = 70, j = 7], [i = 77, j = 79] ] */ ``` 當您定義比較方法時，您有責任決定將一個對象與另一個對象進行比較意味著什么。這里，在比較中只使用i值和j值將被忽略。 **get()** 方法通過使用隨機值初始化CompType對象來構建它們。在 **main()** 中，**get()** 與 **Arrays.setAll()** 一起使用，以填充一個 **CompType類型** 數組，然后對其排序。如果沒有實現 **Comparable接口**，那么當您試圖調用 **sort()** 時，您將在運行時獲得一個 **ClassCastException** 。這是因為 **sort()** 將其參數轉換為 **Comparable類型**。現在假設有人給了你一個沒有實現 **Comparable接口** 的類，或者給了你一個實現 **Comparable接口** 的類，但是你不喜歡它的工作方式而愿意有一個不同的對于此類型的比較方法。為了解決這個問題，創建一個實現 **Comparator** 接口的單獨的類(在集合一章中簡要介紹)。它有兩個方法，**compare()** 和 **equals()**。但是，除了特殊的性能需求外，您不需要實現 **equals()**，因為無論何時創建一個類，它都是隱式地繼承自 **Object**，**Object** 有一個equals()。您可以只使用默認的 **Object equals()** 來滿足接口的規范。集合類(注意復數;我們將在下一章節討論它) 包含一個方法 **reverseOrder()**，它生成一個來 **Comparator**（比較器）反轉自然排序順序。這可以應用到比較對象： ```JAVA // arrays/Reverse.java // The Collections.reverseOrder() Comparator import onjava.*; import java.util.Arrays; import java.util.Collections; import static onjava.ArrayShow.*; public class Reverse { public static void main(String[] args) { CompType[] a = new CompType[12]; Arrays.setAll(a, n -> CompType.get()); show("Before sorting", a); Arrays.sort(a, Collections.reverseOrder()); show("After sorting", a); } } /* Output: Before sorting: [[i = 35, j = 37], [i = 41, j = 20], [i = 77, j = 79] , [i = 56, j = 68], [i = 48, j = 93], [i = 70, j = 7], [i = 0, j = 25], [i = 62, j = 34], [i = 50, j = 82] , [i = 31, j = 67], [i = 66, j = 54], [i = 21, j = 6] ] After sorting: [[i = 77, j = 79], [i = 70, j = 7], [i = 66, j = 54] , [i = 62, j = 34], [i = 56, j = 68], [i = 50, j = 82] , [i = 48, j = 93], [i = 41, j = 20], [i = 35, j = 37] , [i = 31, j = 67], [i = 21, j = 6], [i = 0, j = 25] ] */ ``` 您還可以編寫自己的比較器。這個比較CompType對象基于它們的j值而不是它們的i值: ```JAVA // arrays/ComparatorTest.java // Implementing a Comparator for a class import onjava.*; import java.util.Arrays; import java.util.Comparator; import static onjava.ArrayShow.*; class CompTypeComparator implements Comparator<CompType> { public int compare(CompType o1, CompType o2) { return (o1.j < o2.j ? -1 : (o1.j == o2.j ? 0 : 1)); } } public class ComparatorTest { public static void main(String[] args) { CompType[] a = new CompType[12]; Arrays.setAll(a, n -> CompType.get()); show("Before sorting", a); Arrays.sort(a, new CompTypeComparator()); show("After sorting", a); } } /* Output: Before sorting:[[i = 35, j = 37], [i = 41, j = 20], [i = 77, j = 79] , [i = 56, j = 68], [i = 48, j = 93], [i = 70, j = 7] , [i = 0, j = 25], [i = 62, j = 34], [i = 50, j = 82], [i = 31, j = 67], [i = 66, j = 54], [i = 21, j = 6] ] After sorting: [[i = 21, j = 6], [i = 70, j = 7], [i = 41, j = 20] , [i = 0, j = 25], [i = 62, j = 34], [i = 35, j = 37] , [i = 66, j = 54], [i = 31, j = 67], [i = 56, j = 68] , [i = 77, j = 79], [i = 50, j = 82], [i = 48, j = 93] ] */ ```