您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

程序开发中常用的十种算法,你用过几种?

时间:2024-01-17 15:05:28  来源:今日头条  作者:架构师老卢

当编写程序时,了解和使用不同的算法对解决问题至关重要。以下是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("INFt");
                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。最终,我们可以获得所有点对之间的最短路径长度。



Tags:算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除。
▌相关推荐
程序开发中常用的十种算法,你用过几种?
当编写程序时,了解和使用不同的算法对解决问题至关重要。以下是C#中常用的10种算法,每个算法都伴随着示例代码和详细说明。1. 冒泡排序 (Bubble Sort):冒泡排序是一种简单的比...【详细内容】
2024-01-17  Tags: 算法  点击:(0)  评论:(0)  加入收藏
百度最新的搜索引擎算法是什么样的?
百度搜索引擎算法是百度用来决定网页排名的算法。它是百度搜索技术的核心,也是百度作为全球最大的中文搜索引擎的基石。随着互联网的发展和用户需求的不断变化,百度搜索引擎算...【详细内容】
2024-01-10  Tags: 算法  点击:(9)  评论:(0)  加入收藏
百度网站排名算法是什么样的?
一、引言随着互联网的普及,搜索引擎已成为人们获取信息的重要途径。作为国内最大的搜索引擎,百度每天要处理数亿次的搜索请求。在这背后,是百度的排名算法在默默地发挥着作用。...【详细内容】
2024-01-09  Tags: 算法  点击:(14)  评论:(0)  加入收藏
面向推荐系统的深度强化学习算法研究与应用
随着互联网的快速发展,推荐系统在各个领域中扮演着重要的角色。传统的推荐算法在面对大规模、复杂的数据时存在一定的局限性。为了解决这一问题,深度强化学习算法应运而生。本...【详细内容】
2024-01-04  Tags: 算法  点击:(6)  评论:(0)  加入收藏
深入理解机器学习模型的工作原理和算法
机器学习是一种利用数据和算法构建模型,从而实现自动化学习和预测的技术。本文旨在深入探讨机器学习模型的工作原理和算法,包括监督学习、无监督学习和强化学习等。通过了解机...【详细内容】
2024-01-02  Tags: 算法  点击:(7)  评论:(0)  加入收藏
非负矩阵分解算法:从非负数据中提取主题、特征等信息
非负矩阵分解算法(Non-negativeMatrixFactorization,简称NMF)是一种常用的数据分析和特征提取方法,主要用于从非负数据中提取主题、特征等有意义的信息。本文将介绍非负矩阵分解...【详细内容】
2024-01-02  Tags: 算法  点击:(5)  评论:(0)  加入收藏
再谈前端算法,你这回明白了吗?
楔子 -- 青蛙跳台阶一只青蛙一次可以跳上一级台阶,也可以跳上二级台阶,求该青蛙跳上一个n级的台阶总共需要多少种跳法。分析: 当n=1的时候,①只需要跳一次即可;只有一种跳法,即f(...【详细内容】
2023-12-28  Tags: 算法  点击:(19)  评论:(0)  加入收藏
使用生成对抗网络实现图像风格转换的新算法
图像风格转换是计算机视觉领域的一个重要研究方向,它可以将一张图像的风格转换为另一张图像的风格,从而创造出新颖有趣的图像效果。近年来,生成对抗网络(GAN)作为一种强大的图像...【详细内容】
2023-12-15  Tags: 算法  点击:(23)  评论:(0)  加入收藏
强化学习算法在资源调度与优化中的应用
随着云计算和大数据技术的快速发展,资源调度与优化成为了现代计算系统中的重要问题。传统的资源调度算法往往基于静态规则或启发式方法,无法适应动态变化的环境和复杂的任务需...【详细内容】
2023-12-14  Tags: 算法  点击:(42)  评论:(0)  加入收藏
时序分析中的常用算法,都在这里了
时序分析就是利用过去一段时间内某事件时间的特征来预测未来一段时间内该事件的特征。这是一类相对比较复杂的预测建模问题,和回归分析模型的预测不同,时间序列模型是依赖于事...【详细内容】
2023-12-12  Tags: 算法  点击:(34)  评论:(0)  加入收藏
▌简易百科推荐
程序开发中常用的十种算法,你用过几种?
当编写程序时,了解和使用不同的算法对解决问题至关重要。以下是C#中常用的10种算法,每个算法都伴随着示例代码和详细说明。1. 冒泡排序 (Bubble Sort):冒泡排序是一种简单的比...【详细内容】
2024-01-17  架构师老卢  今日头条  Tags:算法   点击:(0)  评论:(0)  加入收藏
百度推荐排序技术的思考与实践
本文将分享百度在推荐排序方面的思考与实践。在整个工业界的推广搜场景上,特征设计通常都是采用离散化的设计,需要保证两方面的效果,一方面是记忆,另一方面是泛化。特征都是通过...【详细内容】
2024-01-09  DataFunTalk  微信公众号  Tags:百度推荐   点击:(6)  评论:(0)  加入收藏
什么是布隆过滤器?如何实现布隆过滤器?
以下我们介绍了什么是布隆过滤器?它的使用场景和执行流程,以及在 Redis 中它的使用,那么问题来了,在日常开发中,也就是在 Java 开发中,我们又将如何操作布隆过滤器呢?布隆过滤器(Blo...【详细内容】
2024-01-05  Java中文社群  微信公众号  Tags:布隆过滤器   点击:(6)  评论:(0)  加入收藏
面向推荐系统的深度强化学习算法研究与应用
随着互联网的快速发展,推荐系统在各个领域中扮演着重要的角色。传统的推荐算法在面对大规模、复杂的数据时存在一定的局限性。为了解决这一问题,深度强化学习算法应运而生。本...【详细内容】
2024-01-04  数码小风向    Tags:算法   点击:(6)  评论:(0)  加入收藏
非负矩阵分解算法:从非负数据中提取主题、特征等信息
非负矩阵分解算法(Non-negativeMatrixFactorization,简称NMF)是一种常用的数据分析和特征提取方法,主要用于从非负数据中提取主题、特征等有意义的信息。本文将介绍非负矩阵分解...【详细内容】
2024-01-02  毛晓峰    Tags:算法   点击:(5)  评论:(0)  加入收藏
再谈前端算法,你这回明白了吗?
楔子 -- 青蛙跳台阶一只青蛙一次可以跳上一级台阶,也可以跳上二级台阶,求该青蛙跳上一个n级的台阶总共需要多少种跳法。分析: 当n=1的时候,①只需要跳一次即可;只有一种跳法,即f(...【详细内容】
2023-12-28  前端爱好者  微信公众号  Tags:前端算法   点击:(19)  评论:(0)  加入收藏
三分钟学习二分查找
二分查找是一种在有序数组中查找元素的算法,通过不断将搜索区域分成两半来实现。你可能在日常生活中已经不知不觉地使用了大脑里的二分查找。最常见的例子是在字典中查找一个...【详细内容】
2023-12-22  小技术君  微信公众号  Tags:二分查找   点击:(21)  评论:(0)  加入收藏
强化学习算法在资源调度与优化中的应用
随着云计算和大数据技术的快速发展,资源调度与优化成为了现代计算系统中的重要问题。传统的资源调度算法往往基于静态规则或启发式方法,无法适应动态变化的环境和复杂的任务需...【详细内容】
2023-12-14  职场小达人欢晓    Tags:算法   点击:(42)  评论:(0)  加入收藏
时序分析中的常用算法,都在这里了
时序分析就是利用过去一段时间内某事件时间的特征来预测未来一段时间内该事件的特征。这是一类相对比较复杂的预测建模问题,和回归分析模型的预测不同,时间序列模型是依赖于事...【详细内容】
2023-12-12  AI超数据  微信公众号  Tags:算法   点击:(34)  评论:(0)  加入收藏
聊一聊雪花算法与分布式ID生成
生成全局唯一ID的雪花算法原理雪花算法是一种用于生成全局唯一ID的算法,最初由Twitter开发,用于解决分布式系统中生成ID的问题。其核心思想是将一个64位的长整型ID划分成多个...【详细内容】
2023-12-12  爱发白日梦的后端  微信公众号  Tags:雪花算法   点击:(38)  评论:(0)  加入收藏
站内最新
站内热门
站内头条