程序開發中常用的十種算法，你用過幾種？
作者：架構師老盧
當編寫程序時，了解和使用不同的算法對解決問題至關重要。以下是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。最終，我們可以獲得所有點對之間的最短路徑長度。
責任編輯：姜華
來源：
今日頭條
