引言
在軟件開發的世界里，算法不僅是程序設計的基礎，更是提升軟件性能、優化用戶體驗的關鍵。Java，作為一種廣泛使用的編程語言，提供了豐富的API和標準庫來支持各種算法的實現。本文將深入探討Java中的排序算法、搜索算法以及一些常見的數據結構，旨在幫助讀者從基礎到高級理解這些算法的原理、實現和應用。

第一部分：排序算法

1. 冒泡排序（Bubble Sort）

冒泡排序是一種簡單的排序算法，時間復雜度為O(n^2)。它的原理是通過重復地遍歷要排序的數列，每次比較相鄰的兩個元素，如果它們的順序錯誤就把它們交換過來。

public class BubbleSort {public static void sort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 交換元素int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}
}

2. 選擇排序（Selection Sort）

選擇排序的工作原理是每次從未排序的元素中選擇最小（或最大）的元素，放在已排序序列的末尾。它的時間復雜度也是O(n^2)。

public class SelectionSort {public static void sort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; i++) {int minIdx = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIdx]) {minIdx = j;}}// 交換元素int temp = arr[minIdx];arr[minIdx] = arr[i];arr[i] = temp;}}
}

3. 插入排序（Insertion Sort）

插入排序的基本操作是將一個數據插入到已排序的有序數據中，從而得到一個新的、元素數增1的有序數據。它的時間復雜度在最壞和平均情況下為O(n^2)，但在接近有序的數據序列中表現出色。

public class InsertionSort {public static void sort(int[] arr) {int n = arr.length;for (int i = 1; i < n; ++i) {int key = arr[i];int j = i - 1;// 將key插入到已排序的子序列中while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key;}}
}

4. 快速排序（Quick Sort）

快速排序使用分治策略，通過選擇一個元素作為"基準"（pivot），將數組分成小于基準和大于基準的兩部分，然后遞歸地對這兩部分進行排序。其平均時間復雜度為O(n log n)。

public class QuickSort {public static void sort(int[] arr, int low, int high) {if (low < high) {int pi = partition(arr, low, high);sort(arr, low, pi - 1);sort(arr, pi + 1, high);}}private static int partition(int[] arr, int low, int high) {int pivot = arr[high];  int i = (low - 1);  for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;// 交換元素int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 將pivot放到正確的位置int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1;}
}

5. 歸并排序（Merge Sort）

歸并排序也是基于分治策略的工作原理。首先將數組分成兩半，分別排序，然后將兩個有序數組合并成一個有序數組。它的時間復雜度為O(n log n)。

public class MergeSort {public static void sort(int[] arr, int left, int right) {if (left < right) {// 找出中間索引int middle = (left + right) / 2;sort(arr, left, middle);sort(arr, middle + 1, right);// 合并兩個子數組merge(arr, left, middle, right);}}private static void merge(int[] arr, int left, int middle, int right) {// 臨時數組用于存儲合并后的數據int[] temp = new int[right - left + 1];int i = left, j = middle + 1, k = 0;while (i <= middle && j <= right) {if (arr[i] <= arr[j]) {temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}// 如果左邊子數組還有剩余while (i <= middle) {temp[k++] = arr[i++];}// 如果右邊子數組還有剩余while (j <= right) {temp[k++] = arr[j++];}// 將排序好的數據復制回原數組for (i = left; i <= right; i++) {arr[i] = temp[i - left];}}
}

第二部分：搜索算法

1. 線性搜索（Linear Search）

線性搜索是最簡單的搜索算法，它遍歷數組中的每個元素，直到找到目標值或遍歷完所有元素。時間復雜度為O(n)。

public class LinearSearch {public static int search(int[] arr, int target) {for (int i = 0; i < arr.length; i++) {if (arr[i] == target) {return i; // 返回目標所在的索引}}return -1; // 目標不在數組中}
}

2. 二分查找（Binary Search）

二分查找適用于已排序的數組。它的原理是將數組分成兩半，如果查找值等于中間元素，則返回該位置；如果查找值小于中間元素，則在左半部繼續搜索；如果大于，則在右半部繼續搜索。其時間復雜度為O(log n)。

public class BinarySearch {public static int search(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2;// 如果查找值等于中間元素，則返回該位置if (arr[mid] == target) {return mid;}if (arr[mid] < target) {left = mid + 1; // 在右半部繼續搜索} else {right = mid - 1; // 在左半部繼續搜索}}return -1; // 目標不在數組中}
}

第三部分：數據結構

1. 數組（Array）

數組是最基本的數據結構，在Java中，數組可以是基本類型數組或對象數組。數組允許直接通過索引訪問元素，效率高，但大小固定。

int[] arr = new int[10];
arr[0] = 1;

2. 鏈表（Linked List）

鏈表是一種線性結構，元素通過指針連接。Java的集合框架提供了LinkedList類，適用于插入和刪除操作頻繁的場景。

LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);

3. 棧（Stack）

棧是一種后進先出（LIFO）的數據結構。Java中可以通過Stack類或使用Deque接口的實現來實現棧。

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
int popElement = stack.pop();

4. 隊列（Queue）

隊列是一種先進先出（FIFO）的數據結構。Java中可以使用Queue接口及其實現類，如LinkedList。

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
int pollElement = queue.poll();

5. 樹（Tree）和二叉搜索樹（Binary Search Tree, BST）

樹是一種層次結構的數據結構。BST是一種特殊的二叉樹，左子節點的值小于根節點，右子節點的值大于根節點。

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}// 插入方法示例
public void insert(TreeNode root, int value) {if (root == null) {root = new TreeNode(value);return;}if (value < root.val) {if (root.left == null) {root.left = new TreeNode(value);} else {insert(root.left, value);}} else {if (root.right == null) {root.right = new TreeNode(value);} else {insert(root.right, value);}}
}

6. 圖（Graph）

圖由節點和連接這些節點的邊組成。在Java中，圖可以用鄰接矩陣或鄰接表表示。

class Graph {private int V; // 節點數private List<List<Integer>> adj; // 鄰接表Graph(int v) {V = v;adj = new ArrayList<>(v);for (int i = 0; i < v; ++i)adj.add(new ArrayList<>());}void addEdge(int v, int w) {adj.get(v).add(w); // 添加邊 v -> w}
}

以下是一些額外的Java代碼示例，涵蓋了更多算法和數據結構的實現，以補充前文中的內容：

排序算法補充
6. 堆排序（Heap Sort）

堆排序利用堆這種數據結構進行排序。堆是一種完全二叉樹，父節點的鍵值總是保持在子節點之上（最大堆）或之下（最小堆）。這里我們將實現一個最大堆排序。

public class HeapSort {public static void sort(int[] arr) {int n = arr.length;// 構建最大堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 一個一個地從堆中提取元素for (int i = n - 1; i > 0; i--) {// 將當前最大值 (根節點) 移到數組末尾int temp = arr[0];arr[0] = arr[i];arr[i] = temp;// 重新調整堆heapify(arr, i, 0);}}// 調整為最大堆private static void heapify(int[] arr, int n, int i) {int largest = i; // 初始化最大值為根節點int left = 2 * i + 1;int right = 2 * i + 2;// 如果左子節點比根節點大，則設置最大值為左子節點if (left < n && arr[left] > arr[largest]) {largest = left;}// 如果右子節點比當前最大值大，則設置最大值為右子節點if (right < n && arr[right] > arr[largest]) {largest = right;}// 如果最大值不是根節點，則交換它們if (largest != i) {int swap = arr[i];arr[i] = arr[largest];arr[largest] = swap;// 遞歸調整受影響的子樹heapify(arr, n, largest);}}
}

搜索算法補充
3. 跳躍搜索（Jump Search）

跳躍搜索適用于排序數組，它通過跳躍一定步長（通常是\sqrt{n}）來搜索元素，然后在找到的塊中進行線性搜索。

public class JumpSearch {public static int search(int[] arr, int x) {int n = arr.length;// 計算步長int step = (int)Math.floor(Math.sqrt(n));int prev = 0;// 找到塊，其中元素可能存在while (arr[Math.min(step, n) - 1] < x) {prev = step;step += (int)Math.floor(Math.sqrt(n));if (prev >= n) {return -1;}}// 執行線性搜索while (arr[prev] < x) {prev++;if (prev == Math.min(step, n)) {return -1;}}// 如果找到元素，則返回其索引if (arr[prev] == x) {return prev;}return -1;}
}

數據結構補充
7. 哈希表（HashMap）

Java中的HashMap是基于哈希表的數據結構，提供快速的存取操作。以下是如何使用HashMap來實現一個簡單的字頻統計功能：

import java.util.HashMap;
import java.util.Map;public class WordFrequency {public static void main(String[] args) {String text = "Java is fun. Java is simple. Java is powerful.";Map<String, Integer> wordFrequency = new HashMap<>();// 清洗文本，轉換為小寫并按空格分割String[] words = text.toLowerCase().split("\\s+");// 統計每個單詞的頻率for (String word : words) {// 移除標點符號word = word.replaceAll("[^a-zA-Z]", "");if (!word.isEmpty()) {wordFrequency.put(word, wordFrequency.getOrDefault(word, 0) + 1);}}// 輸出結果for (Map.Entry<String, Integer> entry : wordFrequency.entrySet()) {System.out.println(entry.getKey() + ": " + entry.getValue());}}
}

8. 二叉堆（Binary Heap）

二叉堆可以用于實現優先級隊列。下面是實現一個最小堆（Min Heap）的例子：

import java.util.ArrayList;
import java.util.List;public class MinHeap {private List<Integer> heap;public MinHeap() {this.heap = new ArrayList<>();}public void insert(int value) {heap.add(value);int current = heap.size() - 1;while (current > 0 && heap.get(parent(current)) > heap.get(current)) {swap(current, parent(current));current = parent(current);}}public int extractMin() {if (heap.isEmpty()) {throw new IllegalStateException("Heap is empty");}int min = heap.get(0);int last = heap.remove(heap.size() - 1);if (!heap.isEmpty()) {heap.set(0, last);heapifyDown(0);}return min;}private void heapifyDown(int index) {int minIndex = index;int left = leftChild(index);if (left < heap.size() && heap.get(left) < heap.get(minIndex)) {minIndex = left;}int right = rightChild(index);if (right < heap.size() && heap.get(right) < heap.get(minIndex)) {minIndex = right;}if (index != minIndex) {swap(index, minIndex);heapifyDown(minIndex);}}private void swap(int i, int j) {int temp = heap.get(i);heap.set(i, heap.get(j));heap.set(j, temp);}private int parent(int i) {return (i - 1) / 2;}private int leftChild(int i) {return 2 * i + 1;}private int rightChild(int i) {return 2 * i + 2;}
}