Java 中排序連結串列

Java 中的連結串列是一種資料結構或集合，允許使用者在記憶體中建立動態陣列。該列表不包含任何預定義的大小。它動態地建立節點並在單個記憶體地址中儲存值和對下一個節點的引用。列表元素按順序保留值，或者列表保持插入元素的插入順序。

排序被定義為以一定順序排列資料結構中的元素的方法。根據要求，排列可以是升序或降序。請注意，可以有多種方法來對列表集合進行排序。

下面是對陣列中的元素進行排序的程式碼塊。

import java.text.Collator;
import java.util.Comparator;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<String>();
        list.add("ab");
        list.add("bb");
        list.add("aA");
        list.add("bB");
        System.out.println(list);
        list.sort(new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return Collator.getInstance().compare(s1, s2);
            }
        });
        System.out.println(list);
    }
}

在上面的程式碼塊中，使用 new 關鍵字例項化了一個列表。關鍵字例項化 String 資料型別的連結串列並在內部呼叫建構函式。然後，列表例項呼叫 add 方法來填充列表中的元素。該值被列印以檢查插入順序。

sort 方法存在於 List 介面中。該函式根據作為引數給出的一些比較器對列表進行排序。比較器用於比較傳遞的元素列表。

你應該考慮的一點是對傳遞的值進行排序並確保它們必須屬於同一型別。如果值的型別不同或元素不可比較，則該類將丟擲 ClassCastException。

排序的內部實現是使用 merge sort 命令完成的，該命令足夠有效並且在 log n 時間內進行比較。所以形成了一個 new Comparator 例項，它覆蓋了 compare 方法。實現是方法覆蓋和提供實現的傳統方式。

相反，可以使用使用 Java 8 lambda 函式的單行實現。該介面是一個函式式介面，只有一個方法可以呼叫。lambda 直接獲取介面中存在的引數數量。上面程式碼的單行 Java 8 表示如下所示。

list.sort((o1, o2) -> Collator.getInstance().compare(o1, o2));

比較列表中元素的實際語句是 collator 類。這個類本質上是抽象的，定義了方法的原型。實現存在於擴充套件它們的抽象類中。

collator 類比較區域設定敏感的字串。getInstance 方法獲取具有當前預設 Locale 值的例項。compare 函式比較基於 collator 的值，並根據大於、小於或等於的值返回 +1、-1 或 0。

上面程式碼的輸出如下所示。第二行表示排列形式的輸出。根據鍵盤上字元的 ASCII 序列，大寫字母的範圍（A-Z）高於小字母（a-z）。因此，第二行中的結果列表首先列印小寫 bb，然後列印 bB，因為它有大寫字母。

[ab, bb, aA, bB]
[aA, ab, bb, bB]