Android學習總結之算法篇三（排序）

歸并排序原理

歸并排序（Merge Sort）是一種采用分治法（Divide and Conquer）的排序算法，其基本思想是將一個大問題分解為多個小問題，分別解決這些小問題，然后將小問題的解合并起來得到原問題的解。具體步驟如下：

分解（Divide）：將待排序的數組從中間分成兩個子數組，遞歸地對這兩個子數組繼續進行分解，直到每個子數組中只有一個元素（因為單個元素的數組本身就是有序的）。
解決（Conquer）：對每個子數組進行排序，由于每個子數組只有一個元素，所以這一步實際上已經完成了排序。
合并（Merge）：將兩個已排序的子數組合并成一個新的有序數組。重復這個合并過程，直到所有的子數組合并成一個完整的有序數組。

代碼實現及注釋

下面是用 Java 實現的歸并排序代碼，并帶有詳細的注釋：

public class MergeSort {// 歸并排序的主函數public static void mergeSort(int[] arr) {if (arr == null || arr.length <= 1) {return; // 如果數組為空或只有一個元素，無需排序}int[] temp = new int[arr.length]; // 創建一個臨時數組，用于合并過程mergeSort(arr, 0, arr.length - 1, temp);}// 遞歸進行歸并排序private static void mergeSort(int[] arr, int left, int right, int[] temp) {if (left < right) {int mid = left + (right - left) / 2; // 計算中間位置// 遞歸排序左半部分mergeSort(arr, left, mid, temp);// 遞歸排序右半部分mergeSort(arr, mid + 1, right, temp);// 合并兩個已排序的子數組merge(arr, left, mid, right, temp);}}// 合并兩個已排序的子數組private static void merge(int[] arr, int left, int mid, int right, int[] temp) {int i = left; // 左子數組的起始索引int j = mid + 1; // 右子數組的起始索引int k = left; // 臨時數組的起始索引// 比較左右子數組的元素，將較小的元素放入臨時數組while (i <= mid && j <= right) {if (arr[i] <= arr[j]) {temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}// 將左子數組中剩余的元素復制到臨時數組while (i <= mid) {temp[k++] = arr[i++];}// 將右子數組中剩余的元素復制到臨時數組while (j <= right) {temp[k++] = arr[j++];}// 將臨時數組中的元素復制回原數組for (k = left; k <= right; k++) {arr[k] = temp[k];}}public static void main(String[] args) {int[] arr = {9, 5, 7, 1, 3, 8, 4, 2, 6};mergeSort(arr);for (int num : arr) {System.out.print(num + " ");}}
}

100000個數字中，對前10000小的數字進行排序（堆排）

import java.util.Arrays;
import java.util.PriorityQueue;public class SortTop10000Smallest {/*** 從給定的數字數組中找出前 10000 小的數字** @param numbers 包含 100000 個數字的數組* @return 包含前 10000 小數字的數組*/public static int[] getTop10000Smallest(int[] numbers) {// 創建一個最大堆，堆的大小為 10000。// 通過自定義比較器 (a, b) -> b - a 來實現最大堆，即堆頂元素為堆中最大的元素PriorityQueue<Integer> maxHeap = new PriorityQueue<>(10000, (a, b) -> b - a);// 遍歷給定的數字數組for (int num : numbers) {if (maxHeap.size() < 10000) {// 如果堆的大小小于 10000，直接將當前數字加入堆中maxHeap.offer(num);} else if (num < maxHeap.peek()) {// 如果堆的大小已經達到 10000，且當前數字小于堆頂元素// 則移除堆頂元素（即當前堆中的最大元素），并將當前數字加入堆中maxHeap.poll();maxHeap.offer(num);}}// 創建一個大小為 10000 的數組，用于存儲最終的前 10000 小的數字int[] top10000 = new int[10000];// 從數組的最后一個位置開始，將堆中的元素依次取出放入數組中for (int i = 9999; i >= 0; i--) {top10000[i] = maxHeap.poll();}return top10000;}public static void main(String[] args) {// 生成一個包含 100000 個隨機數字的數組，數字范圍在 0 到 999999 之間int[] numbers = new int[100000];for (int i = 0; i < 100000; i++) {numbers[i] = (int) (Math.random() * 1000000);}// 調用 getTop10000Smallest 方法，獲取前 10000 小的數字int[] top10000 = getTop10000Smallest(numbers);// 對前 10000 小的數字進行排序，使用 Arrays 類的 sort 方法Arrays.sort(top10000);// 遍歷排序后的數組，打印每個數字for (int num : top10000) {System.out.println(num);}}
}

代碼解釋

最大堆的創建：使用?PriorityQueue?來創建一個最大堆，堆的大小為 10000。通過自定義比較器?(a, b) -> b - a?來實現最大堆。
遍歷數字數組：遍歷 100000 個數字，若堆的大小小于 10000，直接將數字加入堆中；若當前數字小于堆頂元素，移除堆頂元素并加入當前數字。
將堆中的元素轉換為數組：遍歷堆，將堆中的元素依次取出放入數組中。
對前 10000 小的數字進行排序：使用?Arrays.sort?方法對數組進行排序。
打印排序后的結果：遍歷排序后的數組，打印每個元素。

?二叉樹中最近公共祖先（LCA）

二叉樹節點定義

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}

最近公共祖先算法（遞歸解法）

public class LowestCommonAncestor {// 主函數：查找 p 和 q 的最近公共祖先public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 遞歸終止條件：當前節點為空，或找到 p 或 q（自己也是自己的祖先）if (root == null || root == p || root == q) {return root;}// 遞歸查找左子樹和右子樹TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);// 情況 1：左子樹和右子樹都找到節點 → 說明當前根節點是 LCAif (left != null && right != null) {return root;}// 情況 2：左子樹找到節點，右子樹沒找到 → 返回左子樹的結果（可能是 p/q 或它們的祖先）else if (left != null) {return left;}// 情況 3：右子樹找到節點，左子樹沒找到 → 返回右子樹的結果else {return right;}}// 測試用例public static void main(String[] args) {// 構建示例二叉樹TreeNode root = new TreeNode(3);root.left = new TreeNode(5);root.right = new TreeNode(1);root.left.left = new TreeNode(6);root.left.right = new TreeNode(2);root.right.left = new TreeNode(0);root.right.right = new TreeNode(8);root.left.right.left = new TreeNode(7);root.left.right.right = new TreeNode(4);LowestCommonAncestor solution = new LowestCommonAncestor();// 測試案例 1：p=5, q=1 → LCA 是 root(3)TreeNode p = root.left; // val=5TreeNode q = root.right; // val=1System.out.println("LCA of 5 and 1 is: " + solution.lowestCommonAncestor(root, p, q).val); // 輸出 3// 測試案例 2：p=5, q=4 → LCA 是 5q = root.left.right.right; // val=4System.out.println("LCA of 5 and 4 is: " + solution.lowestCommonAncestor(root, p, q).val); // 輸出 5// 測試案例 3：p=7, q=4 → LCA 是 2TreeNode p2 = root.left.right.left; // val=7q = root.left.right.right; // val=4System.out.println("LCA of 7 and 4 is: " + solution.lowestCommonAncestor(root, p2, q).val); // 輸出 2}
}

算法原理（遞歸三要素）

終止條件：
- 當前節點為空（root == null）：說明沒找到，返回?null
- 當前節點是?p?或?q：直接返回自己（自己是自己的祖先）
遞歸邏輯：
- 分別在左子樹和右子樹中查找?p?和?q?的祖先
- 若左子樹和右子樹都找到節點 → 說明當前節點是它們的公共祖先（因為左子樹和右子樹各有一個節點，當前節點是最近的公共祖先）
- 若只有左子樹找到 → 結果在左子樹中（可能是?p/q?或它們的祖先）
- 若只有右子樹找到 → 結果在右子樹中
合并結果：
通過遞歸的返回值，自底向上判斷當前節點是否為 LCA，最終返回最近的那個祖先。

算法特點

時間復雜度：O (n)，每個節點最多被訪問一次
空間復雜度：O (n)（遞歸棧空間，最壞情況下樹退化為鏈表）
適用場景：二叉樹（無論是否為二叉搜索樹），且節點值唯一，p 和 q 一定存在于樹中

關鍵思路

分治思想：將問題分解為左子樹和右子樹的子問題，通過子問題的解合并得到原問題的解
后序遍歷：先處理左右子樹，再處理當前節點，符合 “自底向上” 查找祖先的邏輯
唯一性假設：利用 “樹中節點值唯一” 的特性，直接通過節點引用判斷是否為 p 或 q

找View樹的最近公共祖先?

// 定義 View 類
class View {View[] childs;View parent;public View() {this.childs = null;this.parent = null;}
}public class ViewTreeLCA {// 查找兩個 View 的最近公共祖先public static View findLowestCommonAncestor(View view1, View view2) {// 存儲 view1 到根節點的路徑java.util.HashSet<View> path = new java.util.HashSet<>();// 從 view1 開始，將其到根節點的路徑上的所有 View 加入到 path 集合中View current = view1;while (current != null) {path.add(current);current = current.parent;}// 從 view2 開始，沿著其父節點向上遍歷current = view2;while (current != null) {// 如果當前 View 已經在 path 集合中，說明找到了最近公共祖先if (path.contains(current)) {return current;}current = current.parent;}// 如果沒有找到公共祖先，返回 nullreturn null;}public static void main(String[] args) {// 構建一個簡單的 View 樹View root = new View();View child1 = new View();View child2 = new View();View grandChild1 = new View();View grandChild2 = new View();root.childs = new View[]{child1, child2};child1.parent = root;child2.parent = root;child1.childs = new View[]{grandChild1};grandChild1.parent = child1;child2.childs = new View[]{grandChild2};grandChild2.parent = child2;// 查找 grandChild1 和 grandChild2 的最近公共祖先View lca = findLowestCommonAncestor(grandChild1, grandChild2);if (lca != null) {System.out.println("最近公共祖先是存在的。");} else {System.out.println("未找到最近公共祖先。");}}
}

代碼思路：

存儲路徑：首先，從?view1?開始，沿著其父節點向上遍歷，將經過的所有?View?存儲在一個?HashSet?中，這個集合記錄了?view1?到根節點的路徑。
查找公共祖先：接著，從?view2?開始，同樣沿著其父節點向上遍歷。對于每個經過的?View，檢查它是否已經在之前存儲的路徑集合中。如果存在，說明找到了最近公共祖先，返回該?View。
未找到情況：如果遍歷完?view2?到根節點的路徑都沒有找到公共祖先，返回?null。