（待修改）

1. 雙指針

雙指針是一種常用的算法思想，在解決各類編程問題中應用廣泛。按照指向序列的不同，可分為指向同一序列和指向不同序列這兩類雙指針，部分類型還具有可擴展性：

1. 指向同一序列的雙指針
   • 快慢指針：兩個指針在同一序列中，快指針每次移動的步長大于慢指針，常用于解決鏈表相關問題，如判斷鏈表是否成環（如141.環形鏈表）、尋找鏈表的中點（如143.重排鏈表）等。在判斷鏈表是否成環時，快指針每次移動兩步，慢指針每次移動一步，如果快指針和慢指針相遇，則說明鏈表有環。這種方式可以在不使用額外數據結構的情況下高效解決問題，具有較好的擴展性，比如在142.環形鏈表II中，通過快慢指針相遇后的進一步操作，能找到鏈表開始入環的第一個節點 。
   • 首尾指針：一個指針指向序列頭部，另一個指針指向序列尾部，然后向中間移動，常用于數組相關問題。像11.盛最多水的容器，通過首尾指針不斷調整柱子位置來計算最大盛水量；15.三數之和中，排序后用首尾指針在數組中查找滿足條件的三元組，這種類型在處理有序數組的組合問題時經常使用，通過移動指針可以減少不必要的計算，提高算法效率，也可擴展到四數之和（18.四數之和 ）等問題，增加一層循環，在固定兩個數的情況下，利用首尾指針查找另外兩個數。
   • 固定間距指針：兩個指針在序列中保持固定的間距移動，例如在26.刪除有序數組中的重復項中，快慢指針間距為1，用于原地刪除重復元素，記錄不重復元素的位置。這種指針類型在處理有序數組的去重或特殊元素篩選問題時很有效，在一些需要對數組元素進行特殊處理且元素相對順序固定的場景下，可通過調整間距來滿足需求，具有一定的擴展性 。
2. 指向不同序列的雙指針：主要用于合并或比較不同序列，如歸并排序。在88.合并兩個有序數組中，兩個指針分別指向兩個有序數組，從后往前進行歸并，將較大的數依次放在nums1的后面。這種類型在處理多個有序序列的合并問題時非常高效，并且可以擴展到多個有序序列的合并，通過增加指針數量和相應的比較邏輯來實現 。

using System;class DoublePointerExample
{static void Main(){int[] nums = { 1, 2, 3, 4, 5 };int target = 7;for (int i = 0, j = nums.Length - 1; i < j;){int sum = nums[i] + nums[j];if (sum == target){Console.WriteLine($"找到滿足條件的元素對: {nums[i]}, {nums[j]}");break;}else if (sum < target){i++;}else{j--;}}}
}

2. 滑動窗口

滑動窗口是一種在數組或字符串上常用的算法技巧，通過動態調整窗口的起始和結束位置，來解決一系列與子串、子數組相關的問題。它可以將時間復雜度從暴力解法的$O(n^2)$降低到$O(n)$，提高算法效率。下面為你詳細介紹滑動窗口的相關內容：

理論基礎

滑動窗口本質上是一個連續的子數組（或子串），在數組或字符串上滑動。通過調整窗口的左右邊界，可以在遍歷過程中動態地獲取不同的子數組（或子串），并對其進行處理。其關鍵在于如何根據具體問題，確定窗口的擴展和收縮條件，從而高效地找到滿足條件的子數組（或子串）。

using System;class SlidingWindowExample
{static void Main(){int[] nums = { 1, 3, -1, -3, 5, 3, 6, 7 };int k = 3;for (int i = 0; i <= nums.Length - k; i++){int sum = 0;for (int j = i; j < i + k; j++){sum += nums[j];}Console.WriteLine($"窗口 [{i}, {i + k - 1}] 的和: {sum}");}}
}

3. 二分查找

3. 二分查找

二分查找，也被稱為折半查找，是一種高效的查找算法，專門用于在有序數組中快速定位目標元素。它的核心思想是利用數組的有序性，每次將查找范圍縮小一半，從而顯著提高查找效率。相較于順序查找平均$O(n)$的時間復雜度，二分查找的時間復雜度為$O(\log n)$ ，在處理大規模數據時優勢明顯。

理論基礎

二分查找的前提是數組必須有序。在查找過程中，首先設定兩個指針，通常命名為left和right，分別指向數組的開頭和結尾。接著計算中間位置mid，通過比較目標元素與中間位置元素的大小關系來決定下一步的查找方向。如果目標元素等于中間元素，則查找成功；若目標元素小于中間元素，說明目標元素可能在左半部分，于是將right指針移動到mid - 1位置，繼續在左半部分查找；反之，若目標元素大于中間元素，則將left指針移動到mid + 1位置，在右半部分繼續查找。不斷重復上述步驟，直到找到目標元素或者left超過right（表示未找到目標元素）為止。

using System;class Program
{static int BinarySearchFirst(int[] arr, int target, int left, int right){if (left > right) return -1;int mid = left + (right - left) / 2;if (arr[mid] == target){int prev = BinarySearchFirst(arr, target, left, mid - 1);return prev != -1 ? prev : mid;}else if (arr[mid] < target){return BinarySearchFirst(arr, target, mid + 1, right);}return BinarySearchFirst(arr, target, left, mid - 1);}static void Main(){int[] arr = { 1, 2, 2, 2, 3, 4, 5 };int target = 2;int result = BinarySearchFirst(arr, target, 0, arr.Length - 1);Console.WriteLine(result != -1 ? $"首個 {target} 的索引是 {result}" : $"未找到 {target}");}
}    

4. KMP

KMP 算法用于在主字符串中查找模式字符串，通過預處理模式字符串來減少不必要的比較。

using System;class KMPExample
{static int[] ComputeLPSArray(string pattern){int[] lps = new int[pattern.Length];int len = 0;lps[0] = 0;int i = 1;while (i < pattern.Length){if (pattern[i] == pattern[len]){len++;lps[i] = len;i++;}else{if (len != 0){len = lps[len - 1];}else{lps[i] = 0;i++;}}}return lps;}static int KMPSearch(string text, string pattern){int[] lps = ComputeLPSArray(pattern);int i = 0;int j = 0;while (i < text.Length){if (pattern[j] == text[i]){i++;j++;}if (j == pattern.Length){return i - j;}else if (i < text.Length && pattern[j] != text[i]){if (j != 0){j = lps[j - 1];}else{i++;}}}return -1;}static void Main(){string text = "ABABDABACDABABCABAB";string pattern = "ABABCABAB";int result = KMPSearch(text, pattern);if (result != -1){Console.WriteLine($"模式字符串在主字符串中的起始索引是: {result}");}else{Console.WriteLine($"未找到模式字符串");}}
}

5. 回溯算法

回溯算法用于解決組合、排列等問題，通過深度優先搜索并在不滿足條件時回溯來找到所有可能的解。

using System;
using System.Collections.Generic;class BacktrackingExample
{static void Backtrack(int[] nums, int index, List<List<int>> result, List<int> currentList){result.Add(new List<int>(currentList));for (int i = index; i < nums.Length; i++){currentList.Add(nums[i]);Backtrack(nums, i + 1, result, currentList);currentList.RemoveAt(currentList.Count - 1);}}static List<List<int>> Subsets(int[] nums){List<List<int>> result = new List<List<int>>();Backtrack(nums, 0, result, new List<int>());return result;}static void Main(){int[] nums = { 1, 2, 3 };List<List<int>> subsets = Subsets(nums);foreach (var subset in subsets){Console.Write("[ ");foreach (var num in subset){Console.Write(num + " ");}Console.WriteLine("]");}}
}

6. 貪心算法

貪心算法在每一步選擇中都采取當前狀態下最優的選擇，從而希望得到全局最優解。

using System;class GreedyExample
{static int CoinChange(int[] coins, int amount){int count = 0;Array.Sort(coins);for (int i = coins.Length - 1; i >= 0; i--){while (amount >= coins[i]){amount -= coins[i];count++;}}return amount == 0? count : -1;}static void Main(){int[] coins = { 1, 2, 5 };int amount = 11;int result = CoinChange(coins, amount);Console.WriteLine($"最少需要 {result} 枚硬幣");}
}

7. 動態規劃

動態規劃通過將問題分解為子問題，并保存子問題的解來避免重復計算。

7.1. 01背包

01 背包問題是在給定容量的背包中選擇物品，使總價值最大，每個物品只能選擇一次。

using System;class Knapsack01Example
{static int Knapsack01(int[] weights, int[] values, int capacity){int n = weights.Length;int[,] dp = new int[n + 1, capacity + 1];for (int i = 0; i <= n; i++){for (int w = 0; w <= capacity; w++){if (i == 0 || w == 0){dp[i, w] = 0;}else if (weights[i - 1] <= w){dp[i, w] = Math.Max(values[i - 1] + dp[i - 1, w - weights[i - 1]], dp[i - 1, w]);}else{dp[i, w] = dp[i - 1, w];}}}return dp[n, capacity];}static void Main(){int[] weights = { 2, 3, 4, 5 };int[] values = { 3, 4, 5, 6 };int capacity = 8;int result = Knapsack01(weights, values, capacity);Console.WriteLine($"01 背包的最大價值是: {result}");}
}

7.2. 完全背包

完全背包問題與 01 背包類似，但每個物品可以選擇多次。

using System;class KnapsackCompleteExample
{static int KnapsackComplete(int[] weights, int[] values, int capacity){int n = weights.Length;int[] dp = new int[capacity + 1];for (int i = 0; i < n; i++){for (int w = weights[i]; w <= capacity; w++){dp[w] = Math.Max(dp[w], dp[w - weights[i]] + values[i]);}}return dp[capacity];}static void Main(){int[] weights = { 2, 3, 4, 5 };int[] values = { 3, 4, 5, 6 };int capacity = 8;int result = KnapsackComplete(weights, values, capacity);Console.WriteLine($"完全背包的最大價值是: {result}");}
}

7.3. 多重背包

多重背包問題中每個物品有一定的數量限制。

using System;class KnapsackMultipleExample
{static int KnapsackMultiple(int[] weights, int[] values, int[] amounts, int capacity){int n = weights.Length;int[,] dp = new int[n + 1, capacity + 1];for (int i = 0; i <= n; i++){for (int w = 0; w <= capacity; w++){if (i == 0 || w == 0){dp[i, w] = 0;}else{for (int k = 0; k <= amounts[i - 1] && k * weights[i - 1] <= w; k++){dp[i, w] = Math.Max(dp[i, w], dp[i - 1, w - k * weights[i - 1]] + k * values[i - 1]);}}}}return dp[n, capacity];}static void Main(){int[] weights = { 2, 3, 4, 5 };int[] values = { 3, 4, 5, 6 };int[] amounts = { 2, 3, 1, 2 };int capacity = 8;int result = KnapsackMultiple(weights, values, amounts, capacity);Console.WriteLine($"多重背包的最大價值是: {result}");}
}

8. 單調棧

單調棧用于解決下一個更大元素、下一個更小元素等問題，棧內元素保持單調遞增或單調遞減。

using System;
using System.Collections.Generic;class MonotonicStackExample
{static int[] NextGreaterElement(int[] nums){int[] result = new int[nums.Length];Stack<int> stack = new Stack<int>();for (int i = nums.Length - 1; i >= 0; i--){while (stack.Count > 0 && stack.Peek() <= nums[i]){stack.Pop();}result[i] = stack.Count == 0? -1 : stack.Peek();stack.Push(nums[i]);}return result;}static void Main(){int[] nums = { 4, 5, 2, 10, 8 };int[] result = NextGreaterElement(nums);foreach (var num in result){Console.Write(num + " ");}}
}

9. 并查集

并查集用于處理不相交集合的合并與查詢問題。

using System;class UnionFindExample
{private int[] parent;private int[] rank;public UnionFindExample(int n){parent = new int[n];rank = new int[n];for (int i = 0; i < n; i++){parent[i] = i;rank[i] = 1;}}public int Find(int x){if (parent[x] != x){parent[x] = Find(parent[x]);}return parent[x];}public void Union(int x, int y){int rootX = Find(x);int rootY = Find(y);if (rootX != rootY){if (rank[rootX] < rank[rootY]){parent[rootX] = rootY;}else if (rank[rootX] > rank[rootY]){parent[rootY] = rootX;}else{parent[rootY] = rootX;rank[rootX]++;}}}static void Main(){UnionFindExample uf = new UnionFindExample(5);uf.Union(0, 1);uf.Union(2, 3);Console.WriteLine($"0 和 1 是否在同一集合: {uf.Find(0) == uf.Find(1)}");Console.WriteLine($"0 和 2 是否在同一集合: {uf.Find(0) == uf.Find(2)}");}
}

10. 圖論

圖論是研究圖的性質和算法的領域，包括廣度優先搜索、深度優先搜索等算法。

10.1. 廣度優先搜索（BFS）

廣度優先搜索用于遍歷圖，從起點開始逐層訪問相鄰節點。

using System;
using System.Collections.Generic;class Graph
{private Dictionary<int, List<int>> adjList;public Graph(){adjList = new Dictionary<int, List<int>>();}public void AddEdge(int u, int v){if (!adjList.ContainsKey(u)){adjList[u] = new List<int>();}if (!adjList.ContainsKey(v)){adjList[v] = new List<int>();}adjList[u].Add(v);adjList[v].Add(u);}public void BFS(int start){bool[] visited = new bool[adjList.Count];Queue<int> queue = new Queue<int>();visited[start] = true;queue.Enqueue(start);while (queue.Count > 0){int current = queue.Dequeue();Console.Write(current + " ");foreach (int neighbor in adjList[current]){if (!visited[neighbor]){visited[neighbor] = true;queue.Enqueue(neighbor);}}}}
}class BFSExample
{static void Main(){Graph graph = new Graph();graph.AddEdge(0, 1);graph.AddEdge(0, 2);graph.AddEdge(1, 2);graph.AddEdge(2, 3);graph.AddEdge(3, 3);Console.WriteLine("廣度優先搜索結果:");graph.BFS(0);}
}

10.2. 深度優先搜索（DFS）

深度優先搜索從起點開始盡可能深地訪問節點，直到無法繼續再回溯。

using System;
using System.Collections.Generic;class Graph
{private Dictionary<int, List<int>> adjList;public Graph(){adjList = new Dictionary<int, List<int>>();}public void AddEdge(int u, int v){if (!adjList.ContainsKey(u)){adjList[u] = new List<int>();}if (!adjList.ContainsKey(v)){adjList[v] = new List<int>();}adjList[u].Add(v);adjList[v].Add(u);}private void DFSUtil(int vertex, bool[] visited){visited[vertex] = true;Console.Write(vertex + " ");if (adjList.ContainsKey(vertex)){foreach (int neighbor in adjList[vertex]){if (!visited[neighbor]){DFSUtil(neighbor, visited);}}}}public void DFS(int start){bool[] visited = new bool[adjList.Count];DFSUtil(start, visited);}
}class DFSExample
{static void Main(){Graph graph = new Graph();graph.AddEdge(0, 1);graph.AddEdge(0, 2);graph.AddEdge(1, 2);graph.AddEdge(2, 3);graph.AddEdge(3, 4);Console.WriteLine("深度優先搜索結果:");graph.DFS(0);}
}

10.3. Dijkstra 算法

Dijkstra 算法用于在帶權有向圖中找到從一個源點到其他所有節點的最短路徑。

using System;
using System.Collections.Generic;class DijkstraExample
{private const int Infinity = int.MaxValue;static int MinDistance(int[] dist, bool[] sptSet, int n){int min = Infinity, minIndex = -1;for (int v = 0; v < n; v++){if (!sptSet[v] && dist[v] <= min){min = dist[v];minIndex = v;}}return minIndex;}static void PrintSolution(int[] dist, int n){Console.WriteLine("Vertex \t Distance from Source");for (int i = 0; i < n; i++){Console.WriteLine(i + " \t\t " + dist[i]);}}static void Dijkstra(int[,] graph, int src, int n){int[] dist = new int[n];bool[] sptSet = new bool[n];for (int i = 0; i < n; i++){dist[i] = Infinity;sptSet[i] = false;}dist[src] = 0;for (int count = 0; count < n - 1; count++){int u = MinDistance(dist, sptSet, n);sptSet[u] = true;for (int v = 0; v < n; v++){if (!sptSet[v] && graph[u, v] != 0 && dist[u] != Infinity && dist[u] + graph[u, v] < dist[v]){dist[v] = dist[u] + graph[u, v];}}}PrintSolution(dist, n);}static void Main(){int n = 5;int[,] graph = {{ 0, 4, 0, 0, 0 },{ 4, 0, 8, 0, 0 },{ 0, 8, 0, 7, 4 },{ 0, 0, 7, 0, 9 },{ 0, 0, 4, 9, 0 }};Console.WriteLine("Shortest distances from source vertex 0:");Dijkstra(graph, 0, n);}
}

10.4. Floyd-Warshall 算法

Floyd-Warshall 算法用于在帶權圖中找到所有頂點對之間的最短路徑。

using System;class FloydWarshallExample
{static void FloydWarshall(int[,] graph, int n){int[,] dist = (int[,])graph.Clone();for (int k = 0; k < n; k++){for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){if (dist[i, k] != int.MaxValue && dist[k, j] != int.MaxValue &&dist[i, k] + dist[k, j] < dist[i, j]){dist[i, j] = dist[i, k] + dist[k, j];}}}}Console.WriteLine("All Pairs Shortest Paths:");for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){if (dist[i, j] == int.MaxValue){Console.Write("INF\t");}else{Console.Write(dist[i, j] + "\t");}}Console.WriteLine();}}static void Main(){int n = 4;int[,] graph = {{ 0, 5, int.MaxValue, 10 },{ int.MaxValue, 0, 3, int.MaxValue },{ int.MaxValue, int.MaxValue, 0, 1 },{ int.MaxValue, int.MaxValue, int.MaxValue, 0 }};FloydWarshall(graph, n);}
}

11. 哈希算法

哈希算法用于將數據映射到固定大小的哈希值，常用于快速查找、數據去重等。

using System;
using System.Collections.Generic;class HashExample
{static void Main(){Dictionary<int, string> hashTable = new Dictionary<int, string>();hashTable[1] = "apple";hashTable[2] = "banana";hashTable[3] = "cherry";if (hashTable.ContainsKey(2)){Console.WriteLine($"Key 2 的值是: {hashTable[2]}");}hashTable[2] = "orange";Console.WriteLine($"更新后 Key 2 的值是: {hashTable[2]}");hashTable.Remove(3);Console.WriteLine("移除 Key 3 后哈希表:");foreach (var pair in hashTable){Console.WriteLine($"Key: {pair.Key}, Value: {pair.Value}");}}
}

12. 排序算法

12.1. 冒泡排序

冒泡排序通過多次比較相鄰元素并交換位置，將最大（或最小）的元素逐步“冒泡”到數組末尾。

using System;class BubbleSortExample
{static void BubbleSort(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;}}}}static void Main(){int[] nums = { 64, 34, 25, 12, 22, 11, 90 };BubbleSort(nums);Console.Write("排序后的數組: ");foreach (int num in nums){Console.Write(num + " ");}}
}

12.2. 選擇排序

選擇排序每次從未排序的元素中找到最小（或最大）的元素，將其放到已排序序列的末尾。

using System;class SelectionSortExample
{static void SelectionSort(int[] arr){int n = arr.Length;for (int i = 0; i < n - 1; i++){int minIndex = i;for (int j = i + 1; j < n; j++){if (arr[j] < arr[minIndex]){minIndex = j;}}int temp = arr[minIndex];arr[minIndex] = arr[i];arr[i] = temp;}}static void Main(){int[] nums = { 64, 34, 25, 12, 22, 11, 90 };SelectionSort(nums);Console.Write("排序后的數組: ");foreach (int num in nums){Console.Write(num + " ");}}
}

12.3. 插入排序

插入排序將一個數據插入到已經排好序的數組中的適當位置，直到整個數組有序。

using System;class InsertionSortExample
{static void InsertionSort(int[] arr){int n = arr.Length;for (int i = 1; i < n; i++){int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key){arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key;}}static void Main(){int[] nums = { 64, 34, 25, 12, 22, 11, 90 };InsertionSort(nums);Console.Write("排序后的數組: ");foreach (int num in nums){Console.Write(num + " ");}}
}

12.4. 希爾排序

希爾排序是對插入排序的改進，通過將數組分成若干個子序列，對每個子序列進行插入排序，逐步縮小間隔，最終使整個數組有序。

using System;class ShellSortExample
{static void ShellSort(int[] arr){int n = arr.Length;for (int gap = n / 2; gap > 0; gap /= 2){for (int i = gap; i < n; i++){int temp = arr[i];int j;for (j = i; j >= gap && arr[j - gap] > temp; j -= gap){arr[j] = arr[j - gap];}arr[j] = temp;}}}static void Main(){int[] nums = { 64, 34, 25, 12, 22, 11, 90 };ShellSort(nums);Console.Write("排序后的數組: ");foreach (int num in nums){Console.Write(num + " ");}}
}

12.5. 歸并排序

歸并排序是一種分治算法，將數組分成兩個子數組，分別排序后再合并成一個有序數組。

using System;class MergeSortExample
{static void Merge(int[] arr, int left, int mid, int right){int n1 = mid - left + 1;int n2 = right - mid;int[] L = new int[n1];int[] R = new int[n2];for (int i = 0; i < n1; i++){L[i] = arr[left + i];}for (int j = 0; j < n2; j++){R[j] = arr[mid + 1 + j];}int i = 0, j = 0, k = left;while (i < n1 && j < n2){if (L[i] <= R[j]){arr[k] = L[i];i++;}else{arr[k] = R[j];j++;}k++;}while (i < n1){arr[k] = L[i];i++;k++;}while (j < n2){arr[k] = R[j];j++;k++;}}static void MergeSort(int[] arr, int left, int right){if (left < right){int mid = left + (right - left) / 2;MergeSort(arr, left, mid);MergeSort(arr, mid + 1, right);Merge(arr, left, mid, right);}}static void Main(){int[] nums = { 64, 34, 25, 12, 22, 11, 90 };MergeSort(nums, 0, nums.Length - 1);Console.Write("排序后的數組: ");foreach (int num in nums){Console.Write(num + " ");}}
}

12.6. 快速排序

快速排序也是一種分治算法，選擇一個基準元素，將數組分為兩部分，使得左邊部分的元素都小于基準，右邊部分的元素都大于基準，然后分別對兩部分遞歸排序。

using System;class QuickSortExample
{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;}}int temp1 = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp1;return i + 1;}static void QuickSort(int[] arr, int low, int high){if (low < high){int pi = Partition(arr, low, high);QuickSort(arr, low, pi - 1);QuickSort(arr, pi + 1, high);}}static void Main(){int[] nums = { 64, 34, 25, 12, 22, 11, 90 };QuickSort(nums, 0, nums.Length - 1);Console.Write("排序后的數組: ");foreach (int num in nums){Console.Write(num + " ");}}
}

以下是繼續完成堆排序以及后面排序算法示例的內容：

12.7. 堆排序

堆排序利用堆這種數據結構來實現排序，將數組構建成一個最大堆（或最小堆），然后依次取出堆頂元素并調整堆，最終得到有序數組。

using System;class HeapSortExample
{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 temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;Heapify(arr, n, largest);}}static void HeapSort(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);}}static void Main(){int[] nums = { 64, 34, 25, 12, 22, 11, 90 };HeapSort(nums);Console.Write("排序后的數組: ");foreach (int num in nums){Console.Write(num + " ");}}
}

12.8. 計數排序

計數排序適用于一定范圍內的整數排序，通過統計每個值出現的次數，再根據統計結果將元素依次放回數組中。

using System;class CountingSortExample
{static void CountingSort(int[] arr){int max = arr[0];foreach (int num in arr){if (num > max){max = num;}}int[] count = new int[max + 1];foreach (int num in arr){count[num]++;}int index = 0;for (int i = 0; i < count.Length; i++){while (count[i] > 0){arr[index++] = i;count[i]--;}}}static void Main(){int[] nums = { 4, 2, 2, 8, 3, 3, 1 };CountingSort(nums);Console.Write("排序后的數組: ");foreach (int num in nums){Console.Write(num + " ");}}
}

12.9. 桶排序

桶排序將數據分到有限數量的桶中，每個桶再分別進行排序（可以使用其他排序算法），最后將各個桶中的元素合并起來得到有序數組。

using System;
using System.Collections.Generic;class BucketSortExample
{static void BucketSort(double[] arr){int numBuckets = 10;List<double>[] buckets = new List<double>[numBuckets];for (int i = 0; i < numBuckets; i++){buckets[i] = new List<double>();}foreach (double num in arr){int bucketIndex = (int)(num * numBuckets);buckets[bucketIndex].Add(num);}int index = 0;for (int i = 0; i < numBuckets; i++){buckets[i].Sort();foreach (double num in buckets[i]){arr[index++] = num;}}}static void Main(){double[] nums = { 0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51 };BucketSort(nums);Console.Write("排序后的數組: ");foreach (double num in nums){Console.Write(num + " ");}}
}

12.10. 基數排序

基數排序從低位到高位依次對數字的每一位進行排序，根據該位的值將數字分配到不同的桶中，再依次收集起來，最終得到有序數組。

using System;class RadixSortExample
{static int GetMax(int[] arr){int max = arr[0];for (int i = 1; i < arr.Length; i++){if (arr[i] > max){max = arr[i];}}return max;}static void CountingSortByDigit(int[] arr, int exp){int[] output = new int[arr.Length];int[] count = new int[10];for (int i = 0; i < arr.Length; i++){count[(arr[i] / exp) % 10]++;}for (int i = 1; i < 10; i++){count[i] += count[i - 1];}for (int i = arr.Length - 1; i >= 0; i--){output[count[(arr[i] / exp) % 10] - 1] = arr[i];count[(arr[i] / exp) % 10]--;}for (int i = 0; i < arr.Length; i++){arr[i] = output[i];}}static void RadixSort(int[] arr){int max = GetMax(arr);for (int exp = 1; max / exp > 0; exp *= 10){CountingSortByDigit(arr, exp);}}static void Main(){int[] nums = { 170, 45, 75, 90, 802, 24, 2, 66 };RadixSort(nums);Console.Write("排序后的數組: ");foreach (int num in nums){Console.Write(num + " ");}}
}

13. 位運算算法

位運算算法是直接對整數在二進制表示上進行操作的算法，常用于高效地處理數據。例如判斷一個數是否為 2 的冪次方：

using System;class BitwiseOperationExample
{static bool IsPowerOfTwo(int num){return (num > 0) && ((num & (num - 1)) == 0);}static void Main(){int number = 8;bool result = IsPowerOfTwo(number);if (result){Console.WriteLine($"{number} 是 2 的冪次方");}else{Console.WriteLine($"{number} 不是 2 的冪次方");}}
}