排序演算法

1. 冒泡排序 (Bubble Sort)
   原理：重複地遍歷數列，比較相鄰元素並交換它們的順序。每次遍歷後，最大或最小的元素會「冒泡」到數列的一端。

• 時間複雜度：
  最壞和平均情況：𝑂(𝑛²)
  最好情況：𝑂(𝑛)（當數列已經排好序）
• 特點：簡單直觀，但效率低下，適合小數據集或教學用途。

2. 選擇排序 (Selection Sort)
   原理：將數列分為已排序和未排序兩部分，重複選擇未排序部分的最小（或最大）元素並將其放置到已排序部分的末尾。

• 時間複雜度：
  所有情況均為 𝑂(𝑛²)
• 特點：雖然簡單，卻不如其他排序算法高效，通常不適合大型數據集。

3. 插入排序 (Insertion Sort)
   原理：將數列分為已排序和未排序兩部分，重複將未排序部分的第一個元素插入到已排序部分的正確位置。

• 時間複雜度：
  最壞情況:O(n²)
  最好情況：𝑂(𝑛)（當數列已經排好序）
• 特點：對於小規模或幾乎已排序的數據非常高效，因為它在大部分情況下可以快速找到插入位置。

4. 快速排序 (Quick Sort)
   原理：選擇一個「基準」元素，將數列分為比基準小和比基準大的兩部分，然後遞迴地對這兩部分進行排序。

• 時間複雜度：
  最壞情況：
  𝑂(𝑛²)（當選擇的基準元素不佳）
  平均情況：𝑂(𝑛log𝑛)
• 特點：在大多數情況下非常高效，且常被用作一般排序的標準方法。選擇好的基準元素（如隨機選擇或三數取中）可以顯著提高性能。

5. 合併排序 (Merge Sort)
   原理：將數列分為兩半，對每一半進行遞迴排序，然後將兩個已排序的部分合併。

• 時間複雜度：
  所有情況均為:O(nlogn)
• 特點：穩定且適合大數據集，特別是在鏈表中表現良好。需要額外的空間來存儲合併結果。

6. 堆排序 (Heap Sort)
   原理：將數列視為一棵完全二叉樹，首先構建一個最大堆，然後重複將最大元素放到數列末尾並調整堆。

• 時間複雜度：
  所有情況均為:O(nlogn)
• 特點：不需要額外的空間，且是基於樹結構的排序方法，適合需要原地排序的情況。

7. 計數排序 (Counting Sort)
   原理：適用於範圍有限的整數，通過計算每個元素出現的次數來構建已排序數列。

• 時間複雜度：
  O(n+k)（其中k是數列中最大元素的值）
• 特點：適合範圍有限的整數，效率高，但不適用於需要排序的範圍過大的情況。

8. 基數排序 (Radix Sort)
   原理：將數據按位進行排序，先按最低位排序，然後按次低位排序，依此類推。

• 時間複雜度：
  O(n⋅k)（其中k 是數字的位數）
• 特點：適合大量整數排序，特別是位數相對較少的情況。

搜尋演算法

1. 線性搜尋 (Linear Search)
   原理：從數據結構的起始位置開始，逐個檢查每個元素，直到找到目標元素或遍歷完所有元素。

• 時間複雜度：
  最壞情況和平均情況均為:𝑂(𝑛)
• 適用情況：適合小數據集或未排序的數據。

2. 二分搜尋 (Binary Search)
   原理：對已排序的數據進行搜尋，首先比較目標元素與中間元素。如果目標元素小於中間元素，則在左半部分繼續搜尋，反之則在右半部分。

• 時間複雜度：
  最壞情況和平均情況均為:𝑂(log𝑛)
• 適用情況：僅適用於已排序的數據。

3. 深度優先搜尋 (Depth-First Search, DFS)
   原理：從一個節點開始，沿著每一個分支深入探索，直到無法繼續為止，然後回溯。

• 時間複雜度：
  對於圖最壞情況為: 𝑂(𝑉+𝐸)，其中 𝑉是節點數量，𝐸是邊的數量。
• 適用情況：適合尋找所有可能的解或遍歷整個圖形結構。

4. 廣度優先搜尋 (Breadth-First Search, BFS)
   原理：從一個節點開始，先探索其所有相鄰節點，再逐層向外擴展。

• 時間複雜度：，
  最壞情況為:O(V+E)。
• 適用情況：適合尋找最短路徑或層級結構的問題。

5. 哈希搜尋 (Hash Search)
   原理：使用哈希表來存儲數據，利用哈希函數快速定位元素的位置。

• 時間複雜度：
  最壞情況為:O(n)
  平均情況下通常為:O(1)。
• 適用情況：當需要快速查找的時候，尤其適合鍵值對查找。

6. 插值搜尋 (Interpolation Search)
   原理：對已排序的數據進行搜尋，根據目標元素的值與數組邊界值的關係，計算預測的中間位置進行搜尋。

• 時間複雜度：
  最壞情況為:𝑂(𝑛)但對於均勻分佈的數據。
  平均情況可以達到:𝑂(loglog𝑛)
• 適用情況：適合數據均勻分佈的已排序數據。