Java 中的搜尋與排序：主要差異與應用

本文比較了 Java 的搜尋和排序演算法，重點介紹了它們獨特的函數、方法和時間複雜度。 它提供了實際的範例和實現，例如用於資料組織的歸併排序和用於高效檢索的二分搜索，展示了它們解決現實世界問題的能力。

在 Java 中，牢牢掌握搜尋和排序演算法及其關鍵差異對於應用程式功能和有效的資料管理至關重要。 搜尋精確定位資料集中的特定數據，而排序則重新排列資料本身。本文透過範例來探討它們在目的、方法和應用上的差異。

Java 的搜尋和排序演算法之間的核心差異在於它們的目標、輸出、效率和時間複雜度。 比較分析請參考表1。

表1 Java 中的搜尋與排序

演算法的選擇通常取決於期望的結果、應用程式需求（資料集大小、預排序資料等）和特定要求。

表 2 說明了幾種搜尋和排序演算法的偽代碼範例和時間複雜度：

表 2 運行時複雜性和偽代碼範例 注意：沒有Java的Comparable接口，程式碼僅適用於原始資料型別。 (資料來源：Lysecky, R. 和 Lizarraga, A. (2022)。使用 ZyLabs 進行 Java 程式設計，18.3 O 表示法，圖 18.3.2。)

合併排序是一種分而治之的演算法，它遞歸地將資料數組分割成更小的子數組，對它們進行排序，然後合併排序後的子數組（GeeksforGeeks，2020a）。 相反，二分搜尋適用於預先排序的數組，反覆將搜尋間隔減半，直到找到目標元素或認為目標元素不存在（GeeksforGeeks，2020b）。

以下範例示範使用合併排序依出版年份對 ArrayList 個 Book 個物件進行排序，然後在排序清單上進行二分搜尋：

Book.java

<code class="language-java">/**
 * Book object with title and publication year. Implements Comparable for year-based sorting.
 * 
 * @author Alexander Ricciardi
 * @version 1.0
 * @date 07/14/2024
 */
class Book implements Comparable<Book> {
    String title;
    int year;

    /**
     * Book constructor.
     * @param title Book title.
     * @param year Publication year.
     */
    public Book(String title, int year) {
        this.title = title;
        this.year = year;
    }

    /**
     * Compares books by publication year.
     * @param other Book to compare.
     * @return Comparison result.
     */
    @Override
    public int compareTo(Book other) {
        return Integer.compare(this.year, other.year);
    }

    /**
     * Returns book's string representation.
     * @return String representation.
     */
    @Override
    public String toString() {
        return title + " (" + year + ")";
    }
}</code>

BookSortingSearching.java

<code class="language-java">import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/**
 * Sorts and searches a list of books using merge sort and binary search.
 * 
 * @author Alexander Ricciardi
 * @version 1.0
 * @date 07/14/2024
 */
public class BookSortingSearching {

    // ... (mergeSort and binarySearch methods remain the same) ...

    public static void main(String[] args) {
        // ... (main method remains largely the same) ...
    }
}</code>

...（mergeSort 和 binarySearch 方法將包含在此處，因為它們在原始輸入中。為了簡潔起見，我省略了它們，因為它們很長並且已經存在。）

輸出（範例）：

... (Original and sorted lists are displayed here) ...
<p>Enter a year to search for: 1951
Book found: The Catcher in the Rye (1951)</p>

歸併排序的O(n log(n))複雜性使其對於大型資料集非常高效，而二分搜尋的目標方法非常適合機器學習等應用（例如，尋找最佳超參數）。

總之，搜尋和排序演算法雖然不同，但卻是相互依賴的。 排序（如合併排序）為高效搜尋（如二分搜尋）準備數據，這使得兩者對於跨不同領域的多樣化問題解決都是不可或缺的。

---

參考文獻：

極客們的極客們。 （2020a，11 月 18 日）。 合併排序。極客們的極客們。 https://www.php.cn/link/d0e7b521c18b09876cb7693e42880dba

極客們的極客們。 （2020b，2 月 3 日）。 二分搜尋。極客們的極客們。 https://www.php.cn/link/d29af1fd577b037033dd1149e816d521

Lysecky, R. 與 Lizarraga, A. (2022)。 使用 ZyLabs 使用 Java 程式設計。 Zyante, Inc.

---

最初由 Level UP Coding 於 2024 年 11 月 22 日在 Medium 上的 Alex.omegapy 發表。

以上是Java 中的搜尋與排序：主要差異與應用的詳細內容。更多資訊請關注PHP中文網其他相關文章！