程式開發中常用的10種演算法，你用過幾種？

来源:https://www.cnblogs.com/hanbing81868164/archive/2023/11/30/17867303.html
-Advertisement-
Play Games

當編寫程式時，瞭解和使用不同的演算法對解決問題至關重要。以下是C#中常用的10種演算法，每個演算法都伴隨著示例代碼和詳細說明。 1. 冒泡排序 (Bubble Sort): 冒泡排序是一種簡單的比較排序演算法，它多次遍曆數組，將較大的元素逐漸浮動到數組的末尾。 public static void Bubb ...


當編寫程式時，瞭解和使用不同的演算法對解決問題至關重要。以下是C#中常用的10種演算法，每個演算法都伴隨著示例代碼和詳細說明。

1. 冒泡排序 (Bubble Sort):

冒泡排序是一種簡單的比較排序演算法，它多次遍曆數組，將較大的元素逐漸浮動到數組的末尾。

public 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;
            }
        }
    }
}

2. 快速排序 (Quick Sort):

快速排序是一種高效的分治排序演算法，它通過選擇一個基準元素並將數組分為較小和較大的兩部分來進行排序。

public static void QuickSort(int[] arr, int low, int high)
{
    if (low < high)
    {
        int partitionIndex = Partition(arr, low, high);
        QuickSort(arr, low, partitionIndex - 1);
        QuickSort(arr, partitionIndex + 1, high);
    }
}

public 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 swap = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = swap;

    return i + 1;
}

3. 合併排序 (Merge Sort):

合併排序是一種穩定的分治排序演算法，它將數組分成兩半，分別排序後再合併。

public static void MergeSort(int[] arr)
{
    int n = arr.Length;
    if (n > 1)
    {
        int mid = n / 2;
        int[] left = new int[mid];
        int[] right = new int[n - mid];

        for (int i = 0; i < mid; i++)
            left[i] = arr[i];
        for (int i = mid; i < n; i++)
            right[i - mid] = arr[i];

        MergeSort(left);
        MergeSort(right);

        int i = 0, j = 0, k = 0;
        while (i < mid && j < (n - mid))
        {
            if (left[i] < right[j])
                arr[k++] = left[i++];
            else
                arr[k++] = right[j++];
        }
        while (i < mid)
            arr[k++] = left[i++];
        while (j < (n - mid))
            arr[k++] = right[j++];
    }
}

4. 二分查找 (Binary Search):

二分查找是一種高效的查找演算法，它要求在有序數組中查找特定元素。

public static int BinarySearch(int[] arr, int target)
{
    int low = 0, high = arr.Length - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}

5. 深度優先搜索 (Depth-First Search, DFS):

DFS 是一種圖遍歷演算法，它從起始節點開始，沿著路徑儘可能深入，然後返回並繼續搜索。

using System;
using System.Collections.Generic;

public class Graph
{
    private int V;
    private List<int>[] adj;

    public Graph(int v)
    {
        V = v;
        adj = new List<int>[v];
        for (int i = 0; i < v; i++)
            adj[i] = new List<int>();
    }

    public void AddEdge(int v, int w)
    {
        adj[v].Add(w);
    }

    public void DFS(int v)
    {
        bool[] visited = new bool[V];
        DFSUtil(v, visited);
    }

    private void DFSUtil(int v, bool[] visited)
    {
        visited[v] = true;
        Console.Write(v + " ");

        foreach (var n in adj[v])
        {
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }
}

6. 廣度優先搜索 (Breadth-First Search, BFS):

BFS 是一種圖遍歷演算法，它從起始節點開始，逐層遍歷，先訪問所有相鄰的節點，然後再逐層擴展。

using System;
using System.Collections.Generic;

public class Graph
{
    private int V;
    private List<int>[] adj;

    public Graph(int v)
    {
        V = v;
        adj = new List<int>[v];
        for (int i = 0; i < v; i++)
            adj[i] = new List<int>();
    }

    public void AddEdge(int v, int w)
    {
        adj[v].Add(w);
    }

    public void BFS(int s)
    {
        bool[] visited = new bool[V];

        Queue<int> queue = new Queue<int>();
        visited[s] = true;
        queue.Enqueue(s);

        while (queue.Count != 0)
        {
            s = queue.Dequeue();
            Console.Write(s + " ");

            foreach (var n in adj[s])
            {
                if (!visited[n])
                {
                    visited[n] = true;
                    queue.Enqueue(n);
                }
            }
        }
    }
}

7. Dijkstra演算法:

Dijkstra演算法是一種用於查找圖中最短路徑的演算法。

public class Dijkstra
{
    private static int V = 9;

    private int MinDistance(int[] dist, bool[] sptSet)
    {
        int min = int.MaxValue;
        int minIndex = 0;

        for (int v = 0; v < V; v++)
        {
            if (!sptSet[v] && dist

[v] <= min)
            {
                min = dist[v];
                minIndex = v;
            }
        }

        return minIndex;
    }

    private void PrintSolution(int[] dist)
    {
        Console.WriteLine("Vertex \t Distance from Source");
        for (int i = 0; i < V; i++)
        {
            Console.WriteLine(i + " \t " + dist[i]);
        }
    }

    public void FindShortestPath(int[,] graph, int src)
    {
        int[] dist = new int[V];
        bool[] sptSet = new bool[V];

        for (int i = 0; i < V; i++)
        {
            dist[i] = int.MaxValue;
            sptSet[i] = false;
        }

        dist[src] = 0;

        for (int count = 0; count < V - 1; count++)
        {
            int u = MinDistance(dist, sptSet);

            sptSet[u] = true;

            for (int v = 0; v < V; v++)
            {
                if (!sptSet[v] && graph[u, v] != 0 && dist[u] != int.MaxValue && dist[u] + graph[u, v] < dist[v])
                {
                    dist[v] = dist[u] + graph[u, v];
                }
            }
        }

        PrintSolution(dist);
    }
}

8. 最小生成樹 (Minimum Spanning Tree, MST) - Prim演算法:

Prim演算法用於找到圖的最小生成樹，它從一個初始頂點開始，逐漸擴展生成樹。

public class PrimMST
{
    private static int V = 5;

    private int MinKey(int[] key, bool[] mstSet)
    {
        int min = int.MaxValue;
        int minIndex = 0;

        for (int v = 0; v < V; v++)
        {
            if (!mstSet[v] && key[v] < min)
            {
                min = key[v];
                minIndex = v;
            }
        }

        return minIndex;
    }

    private void PrintMST(int[] parent, int[,] graph)
    {
        Console.WriteLine("Edge \t Weight");
        for (int i = 1; i < V; i++)
        {
            Console.WriteLine(parent[i] + " - " + i + " \t " + graph[i, parent[i]]);
        }
    }

    public void FindMST(int[,] graph)
    {
        int[] parent = new int[V];
        int[] key = new int[V];
        bool[] mstSet = new bool[V];

        for (int i = 0; i < V; i++)
        {
            key[i] = int.MaxValue;
            mstSet[i] = false;
        }

        key[0] = 0;
        parent[0] = -1;

        for (int count = 0; count < V - 1; count++)
        {
            int u = MinKey(key, mstSet);

            mstSet[u] = true;

            for (int v = 0; v < V; v++)
            {
                if (graph[u, v] != 0 && !mstSet[v] && graph[u, v] < key[v])
                {
                    parent[v] = u;
                    key[v] = graph[u, v];
                }
            }
        }

        PrintMST(parent, graph);
    }
}

9. 最小生成樹 (Minimum Spanning Tree, MST) - Kruskal演算法:

Kruskal演算法也用於找到圖的最小生成樹，它基於邊的權重排序。

using System;
using System.Collections.Generic;

public class Graph
{
    private int V, E;
    private List<Edge> edges;

    public Graph(int v, int e)
    {
        V = v;
        E = e;
        edges = new List<Edge>(e);
    }

    public void AddEdge(int src, int dest, int weight)
    {
        edges.Add(new Edge(src, dest, weight));
    }

    public void KruskalMST()
    {
        edges.Sort();

        int[] parent = new int[V];
        int[] rank = new int[V];

        for (int i = 0; i < V; i++)
        {
            parent[i] = i;
            rank[i] = 0;
        }

        int i = 0;
        int e = 0;

        List<Edge> mst = new List<Edge>();

        while (e < V - 1)
        {
            Edge nextEdge = edges[i++];
            int x = Find(parent, nextEdge.src);
            int y = Find(parent, nextEdge.dest);

            if (x != y)
            {
                mst.Add(nextEdge);
                Union(parent, rank, x, y);
                e++;
            }
        }

        Console.WriteLine("Edges in Minimum Spanning Tree:");
        foreach (var edge in mst)
        {
            Console.WriteLine($"{edge.src} - {edge.dest} with weight {edge.weight}");
        }
    }

    private int Find(int[] parent, int i)
    {
        if (parent[i] == i)
            return i;
        return Find(parent, parent[i]);
    }

    private void Union(int[] parent, int[] rank, int x, int y)
    {
        int xRoot = Find(parent, x);
        int yRoot = Find(parent, y);

        if (rank[xRoot] < rank[yRoot])
            parent[xRoot] = yRoot;
        else if (rank[xRoot] > rank[yRoot])
            parent[yRoot] = xRoot;
        else
        {
            parent[yRoot] = xRoot;
            rank[xRoot]++;
        }
    }
}

public class Edge : IComparable<Edge>
{
    public int src, dest, weight;

    public Edge(int src, int dest, int weight)
    {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }

    public int CompareTo(Edge other)
    {
        return weight - other.weight;
    }
}

10.Floyd-Warshall演算法是一種用於解決所有點對最短路徑的動態規划算法。

下麵是C#中的Floyd-Warshall演算法的實現示例：

using System;

class FloydWarshall
{
    private static int INF = int.MaxValue; // 代表無窮大的值

    public static void FindShortestPath(int[,] graph)
    {
        int V = graph.GetLength(0);

        // 創建一個二維數組dist，用於保存最短路徑的長度
        int[,] dist = new int[V, V];

        // 初始化dist數組
        for (int i = 0; i < V; i++)
        {
            for (int j = 0; j < V; j++)
            {
                dist[i, j] = graph[i, j];
            }
        }

        // 逐個頂點考慮，如果經過k頂點路徑比原路徑短，就更新dist數組
        for (int k = 0; k < V; k++)
        {
            for (int i = 0; i < V; i++)
            {
                for (int j = 0; j < V; j++)
                {
                    if (dist[i, k] != INF && dist[k, j] != INF
                        && dist[i, k] + dist[k, j] < dist[i, j])
                    {
                        dist[i, j] = dist[i, k] + dist[k, j];
                    }
                }
            }
        }

        // 輸出最短路徑矩陣
        Console.WriteLine("最短路徑矩陣：");
        for (int i = 0; i < V; i++)
        {
            for (int j = 0; j < V; j++)
            {
                if (dist[i, j] == INF)
                    Console.Write("INF\t");
                else
                    Console.Write(dist[i, j] + "\t");
            }
            Console.WriteLine();
        }
    }

    static void Main(string[] args)
    {
        int V = 4; // 頂點數
        int[,] graph = {
            {0, 5, INF, 10},
            {INF, 0, 3, INF},
            {INF, INF, 0, 1},
            {INF, INF, INF, 0}
        };

        FindShortestPath(graph);
    }
}

在這個示例中，我們使用Floyd-Warshall演算法來計算給定圖的最短路徑矩陣。該演算法通過考慮逐個中間頂點k，不斷更新最短路徑矩陣dist。最終，我們可以獲得所有點對之間的最短路徑長度。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • go協程、線程的本質，如何協調運作
    大家好，夜鶯項目發佈 v6.4.0 版本，新增全局巨集變數功能，本文為大家簡要介紹一下相關更新內容。 全局巨集變數功能 像 SMTP 的配置中密碼類型的信息，之前都是以明文的方式在頁面展示，夜鶯支持全局巨集變數之後，可以在變數管理配置一個 smtp_password 的密碼類型的變數，在 SMTP 配置頁 ...
  • C++ CryptoPP使用AES加解密
    Crypto++ (CryptoPP) 是一個用於密碼學和加密的 C++ 庫。它是一個開源項目，提供了大量的密碼學演算法和功能，包括對稱加密、非對稱加密、哈希函數、消息認證碼 (MAC)、數字簽名等。Crypto++ 的目標是提供高性能和可靠的密碼學工具，以滿足軟體開發中對安全性的需求。高級加密標準（... ...
  • SpringMvc集成開源流量監控、限流、熔斷降級、負載保護組件Sentinel
    作者查閱了Sentinel官網、51CTO、CSDN、碼農家園、博客園等很多技術文章都沒有很準確的springmvc集成Sentinel的示例，因此整理了本文，主要介紹SpringMvc集成Sentinel ...
  • java集合框架(三)ArrayList常見方法的使用
    ArrayList是Java中的一個動態數組類，可以根據實際需要自動調整數組的大小。ArrayList是基於數組實現的，它內部維護的是一個Object數組，預設初始化容量為10，當添加的元素個數超過了當前容量時，會自動擴容。ArrayList也被廣泛用於Java中的集合框架，例如Java中的List... ...
  • 常用【描述性統計指標】含義(by python)
    統計學有時候會被誤解，好像必須有大量的樣本數據，才能使統計結果有意義。這會讓我們覺得統計學離我們的日常生活很遙遠。 其實，如果數據的準確度高的話，少量的樣本數據同樣能反映出真實的情況。比如，很多國家選舉時不斷做的民意調查，一般做到有效樣本1600多份就夠了，不管你是幾千萬人的小國家，還是數億人的大國 ...
  • C++ 通過CryptoPP計算Hash值
    Crypto++ (CryptoPP) 是一個用於密碼學和加密的 C++ 庫。它是一個開源項目，提供了大量的密碼學演算法和功能，包括對稱加密、非對稱加密、哈希函數、消息認證碼 (MAC)、數字簽名等。Crypto++ 的目標是提供高性能和可靠的密碼學工具，以滿足軟體開發中對安全性的需求。該庫包含了許多... ...
  • 重構這段爛代碼，差點把我整凌亂了...
  • 通過.NET Core+Vue3 實現SignalR即時通訊功能
    .NET Core 和 Vue3 結合使用 SignalR 可以實現強大的實時通訊功能，允許實時雙向通信。在這個示例中，我們將詳細說明如何創建一個簡單的聊天應用程式，演示如何使用 .NET Core SignalR 後端和 Vue3 前端來實現實時通訊功能。 步驟1：準備工作 確保你已經安裝了以下工 ...
一周排行
    -Advertisement-
    Play Games
  • WPF 已知問題 監聽 WMI 事件導致觸摸失效
    示例項目結構 在 Visual Studio 中創建一個 WinForms 應用程式後，項目結構如下所示： MyWinFormsApp/ │ ├───Properties/ │ └───Settings.settings │ ├───bin/ │ ├───Debug/ │ └───Release/ ...
  • [STAThread]特性
    [STAThread] 特性用於需要與 COM 組件交互的應用程式，尤其是依賴單線程模型（如 Windows Forms 應用程式）的組件。在 STA 模式下，線程擁有自己的消息迴圈，這對於處理用戶界面和某些 COM 組件是必要的。 [STAThread] static void Main(stri ...
  • UWP WinUI3 傳入 AddHandler 的 RoutedEventHandler 類型與事件所需不匹配將拋出參數異常
    在WinForm中使用全局異常捕獲處理 在WinForm應用程式中，全局異常捕獲是確保程式穩定性的關鍵。通過在Program類的Main方法中設置全局異常處理，可以有效地捕獲並處理未預見的異常，從而避免程式崩潰。 註冊全局異常事件 [STAThread] static void Main() { / ...
  • .NET 多版本 WinForm 開源控制項庫 SunnyUI
    前言 給大家推薦一款開源的 Winform 控制項庫，可以幫助我們開發更加美觀、漂亮的 WinForm 界面。 項目介紹 SunnyUI.NET 是一個基於 .NET Framework 4.0+、.NET 6、.NET 7 和 .NET 8 的 WinForm 開源控制項庫，同時也提供了工具類庫、擴展 ...
  • .net core8 使用Swagger（附當前源碼）
    說明 該文章是屬於OverallAuth2.0系列文章，每周更新一篇該系列文章（從0到1完成系統開發）。 該系統文章，我會儘量說的非常詳細，做到不管新手、老手都能看懂。 說明：OverallAuth2.0 是一個簡單、易懂、功能強大的許可權+可視化流程管理系統。 有興趣的朋友，請關註我吧(*^▽^*) ...
  • WPF 什麼時候 VisualTreeHelper.GetDescendantBounds 將返回無窮大
    一、下載安裝 1.下載git 必須先下載並安裝git，再TortoiseGit下載安裝 git安裝參考教程：https://blog.csdn.net/mukes/article/details/115693833 2.TortoiseGit下載與安裝 TortoiseGit，Git客戶端，32/6 ...
  • C# 開源教程帶你輕鬆掌握數據結構與演算法
    前言 在項目開發過程中，理解數據結構和演算法如同掌握蓋房子的秘訣。演算法不僅能幫助我們編寫高效、優質的代碼，還能解決項目中遇到的各種難題。 給大家推薦一個支持C#的開源免費、新手友好的數據結構與演算法入門教程：Hello演算法。 項目介紹 《Hello Algo》是一本開源免費、新手友好的數據結構與演算法入門 ...
  • 第22篇 生成proto文件bat腳本
    1.生成單個Proto.bat內容 @rem Copyright 2016, Google Inc. @rem All rights reserved. @rem @rem Redistribution and use in source and binary forms, with or with ...
  • 記一次 .NET某上位機視覺程式 卡死分析
    一：背景 1. 講故事 前段時間有位朋友找到我，說他的窗體程式在客戶這邊出現了卡死，讓我幫忙看下怎麼回事？dump也生成了，既然有dump了那就上 windbg 分析吧。 二：WinDbg 分析 1. 為什麼會卡死 窗體程式的卡死，入口門檻很低，後續往下分析就不一定了，不管怎麼說先用 !clrsta ...
  • 醫學DICOM文件與PACS系統進行數據傳輸
    前言 人工智慧時代，人臉識別技術已成為安全驗證、身份識別和用戶交互的關鍵工具。 給大家推薦一款.NET 開源提供了強大的人臉識別 API，工具不僅易於集成，還具備高效處理能力。 本文將介紹一款如何利用這些API，為我們的項目添加智能識別的亮點。 項目介紹 GitHub 上擁有 1.2k 星標的 C# ...
所有分類