日韩成人免费在线_国产成人一二_精品国产免费人成电影在线观..._日本一区二区三区久久久久久久久不

當前位置:首頁 > 科技  > 軟件

程序開發中常用的十種算法,你用過幾種?

來源: 責編: 時間:2024-01-17 10:13:04 215觀看
導讀1、冒泡排序 (Bubble Sort):冒泡排序是一種簡單的比較排序算法,它多次遍歷數組,將較大的元素逐漸浮動到數組的末尾。public static void BubbleSort(int[] arr){ int n = arr.Length; for (int i = 0; i < n - 1;

Ayu28資訊網——每日最新資訊28at.com

1、冒泡排序 (Bubble Sort):

冒泡排序是一種簡單的比較排序算法,它多次遍歷數組,將較大的元素逐漸浮動到數組的末尾。Ayu28資訊網——每日最新資訊28at.com

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):

快速排序是一種高效的分治排序算法,它通過選擇一個基準元素并將數組分為較小和較大的兩部分來進行排序。Ayu28資訊網——每日最新資訊28at.com

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):

合并排序是一種穩定的分治排序算法,它將數組分成兩半,分別排序后再合并。Ayu28資訊網——每日最新資訊28at.com

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):

二分查找是一種高效的查找算法,它要求在有序數組中查找特定元素。Ayu28資訊網——每日最新資訊28at.com

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 是一種圖遍歷算法,它從起始節點開始,沿著路徑盡可能深入,然后返回并繼續搜索。Ayu28資訊網——每日最新資訊28at.com

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 是一種圖遍歷算法,它從起始節點開始,逐層遍歷,先訪問所有相鄰的節點,然后再逐層擴展。Ayu28資訊網——每日最新資訊28at.com

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算法是一種用于查找圖中最短路徑的算法。Ayu28資訊網——每日最新資訊28at.com

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算法用于找到圖的最小生成樹,它從一個初始頂點開始,逐漸擴展生成樹。Ayu28資訊網——每日最新資訊28at.com

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算法也用于找到圖的最小生成樹,它基于邊的權重排序。Ayu28資訊網——每日最新資訊28at.com

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算法的實現示例:Ayu28資訊網——每日最新資訊28at.com

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。最終,我們可以獲得所有點對之間的最短路徑長度。Ayu28資訊網——每日最新資訊28at.com

本文鏈接:http://www.www897cc.com/showinfo-26-63225-0.html程序開發中常用的十種算法,你用過幾種?

聲明:本網頁內容旨在傳播知識,若有侵權等問題請及時與本網聯系,我們將在第一時間刪除處理。郵件:2376512515@qq.com

上一篇: Python編程在未來的發展和應用方向會有哪些變化和機遇?

下一篇: Java高頻面試題:過濾器和攔截器兩位難兄難弟區別

標簽:
  • 熱門焦點
Top 主站蜘蛛池模板: 海南省| 镶黄旗| 江达县| 图们市| 博罗县| 辽中县| 墨竹工卡县| 南木林县| 财经| 衡东县| 新河县| 青神县| 抚顺县| 崇信县| 德昌县| 洛阳市| 阿克陶县| 察隅县| 缙云县| 龙陵县| 阿瓦提县| 新龙县| 格尔木市| 彭泽县| 祁连县| 婺源县| 日土县| 鄂尔多斯市| 博客| 西盟| 金湖县| 潢川县| 广灵县| 泌阳县| 珠海市| 德令哈市| 长沙市| 肥东县| 蒙阴县| 彩票| 宽城|