為什麼Java中沒有排序列表？

一、簡介

Java 提供了豐富的集合框架，具有各種接口和類，可以滿足不同的數據結構需求。但是，它不提供排序列表的內置實現。在本文中，我們將比較插入排序和按需排序的概念，探討這種缺失背後的原因。

我們還討論了插入排序如何可能破壞List接口的契約，並探索實現排序行為的替代方法。

2. 插入排序和按需排序

要理解為什麼 Java 中不存在排序列表，我們必須首先區分插入排序和按需排序。

2.1.插入排序

插入排序涉及在插入時立即重新排列元素，確保每次添加時的排序順序。有些數據結構確實有這種行為方式。通常，它們的實現基於樹結構，最值得注意的是TreeSet和TreeMap 。

插入排序實現的主要優點是從這種結構中讀取數據的效率。寫入數據的成本更高，因為我們需要在結構中找到正確的位置，有時甚至需要重新排列現有數據。

此成本可能比每次讀取時對整個未排序集合進行排序的成本要小得多。然而，具有多個排序條件的插入排序要復雜得多，並且涉及跟踪多個索引樹結構，使得保存更加複雜和昂貴。

2.2.按需排序

另一方面，按需排序會推遲排序操作，直到用戶明確請求為止。排序讀取的成本很高，因為我們每次都必須對整個集合進行排序。

從好的方面來說，保存數據非常便宜，並且底層數據結構可以更簡單——例如，支持ArrayList的數組。而且，我們可以決定每次按不同的條件排序，甚至根本不排序。

3. 為什麼插入排序會破壞List契約

插入時排序會破壞List接口的約定。 List接口的約定指定元素應按照插入的順序進行維護，從而允許重複。插入排序會通過重新排列元素來違反此約定。此順序對於許多依賴元素順序的列表操作和算法很重要。

通過在每次插入時對列表進行排序，我們將更改元素的順序，並可能破壞List接口中定義的其他方法的預期行為。

4. 實現插入排序

在大多數情況下，我們不應該實現自己的數據結構來實現插入排序。已經有一些集合做得很好，儘管它們基於樹數據結構，而不是線性列表。

4.1.使用具有自然順序的TreeSet

如果我們對自然順序感到滿意並且想要忽略重複項，我們可以使用默認構造函數創建一個TreeSet實例：

TreeSet<Integer> sortedSet = new TreeSet<>();
 sortedSet.add(5);
 sortedSet.add(2);
 sortedSet.add(8);
 sortedSet.add(1);
 System.out.println(sortedSet); // Output: [1, 2, 5, 8]

4.2.將TreeSet與自定義訂單一起使用

我們還可以使用自定義Comparator來實現自定義順序。假設我們有一組字符串，我們想按最後一個字母對它們進行排序：

Comparator<String> customComparator = Comparator.comparing(str -> str.charAt(str.length() - 1));

 TreeSet<String> sortedSet = new TreeSet<>(customComparator);

 sortedSet.add("Canada");
 sortedSet.add("Germany");
 sortedSet.add("Japan");
 sortedSet.add("Sweden");
 sortedSet.add("India");

System.out.println(sortedSet); // Output: [India, Canada, Sweden, Japan, Germany]

5. 實現按需排序

如果我們想使用List接口，我們可以實現按需排序。我們可以通過兩種方式做到這一點：就地排序或創建新的排序列表。

5.1.就地排序

要就地對列表進行排序，我們將使用Collections類中的sort方法。它會改變我們的列表，改變元素的順序：

List<Integer> numbers = new ArrayList<>();
 numbers.add(5);
 numbers.add(2);
 numbers.add(8);
 numbers.add(1);
 System.out.println("Before sorting: " + numbers); // Output: Before sorting: [5, 2, 8, 1]

 Collections.sort(numbers);
 System.out.println("After sorting: " + numbers); // Output: After sorting: [1, 2, 5, 8]

就地排序通常更快、更節省內存，但根據定義，它需要在可變集合上工作，這並不總是可取或不可能的。

5.2.不變異排序

我們還可以在不更改原始集合的情況下對列表進行排序。為此，我們將從列表中創建一個流，對其進行排序，然後將其收集到一個新列表中：

List<Integer> sortedList = numbers.stream().sorted().collect(Collectors.toList());

 System.out.println("After sorting: " + sortedList); // Output: After sorting: [1, 2, 5, 8]
 System.out.println("Original list: " + numbers); // Output: Original list: [5, 2, 8, 1]

我們還可以使用前面段落中的知識，而不是將流的元素收集到新列表中，而是將其收集到TreeSet中。這樣，我們就不需要顯式地對它進行排序TreeSet實現將為我們做到這一點：

TreeSet<Integer> sortedSet = numbers.stream().collect(Collectors.toCollection(() -> new TreeSet<>()));

 System.out.println("After sorting: " + sortedSet); // Output: After sorting: [1, 2, 5, 8]
 System.out.println("Original list: " + numbers); // Output: Original list: [5, 2, 8, 1]

六、總結

在本文中，我們看到 Java 集合框架中沒有內置排序列表實現是一個深思熟慮的決定，它維護了List接口契約。然後，我們研究瞭如果我們想實現插入排序，可以使用哪些數據結構。

最後，如果我們決定使用List接口，我們還學習瞭如何按需排序。