算法方法快速回顾

（待修改）

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 的幂次方");
        }
    }
}