一个开源且全面的C#算法实战教程

前言

算法在计算机科学和程序设计中扮演着至关重要的角色，如在解决问题、优化效率、决策优化、实现计算机程序、提高可靠性以及促进科学融合等方面具有广泛而深远的影响。今天大姚给大家分享一个开源、免费、全面的C#算法实战教程：TheAlgorithms/C-Sharp。

项目介绍

一个C#实现的各种算法集合，这些算法涵盖了计算机科学、数学和统计学、数据科学、机器学习、工程等多个领域。这些实现及其相关文档旨在为教育工作者和学生提供学习资源。因此，可能会找到针对同一目标使用不同算法策略和优化的多种实现。

项目源代码

图片

主要算法包括

• 排序算法：冒泡排序、插入排序、计数排序、快速排序等
• 搜索算法：线性搜索、二分搜索等
• 数值计算：最大公约数、二项式系数、牛顿的平方根计算、欧拉方法等
• 字符串算法：Rabin-Karp 算法、KMP 算法、Manacher 算法等
• 数据结构：链表 (Linked List)、栈 (Stack)、队列 (Queue)、二叉树 (Binary Tree)等
• 图算法：深度优先搜索 (Depth-First Search)、广度优先搜索 (Breadth-First Search)、Dijkstra 最短路径等
• 等等......

插入排序

/// 
///     Class that implements insertion sort algorithm.
/// 
/// Type of array element.
public class InsertionSorter : IComparisonSorter
{
    /// 
    ///     Sorts array using specified comparer,
    ///     internal, in-place, stable,
    ///     time complexity: O(n^2),
    ///     space complexity: O(1),
    ///     where n - array length.
    /// 
    /// Array to sort.
    /// Compares elements.
    public void Sort(T[] array, IComparer comparer)
    {
        for (var i = 1; i  0 && comparer.Compare(array[j], array[j - 1]) < 0; j--)
            {
                var temp = array[j - 1];
                array[j - 1] = array[j];
                array[j] = temp;
            }
        }
    }
}

快速排序

/// 
///     Sorts arrays using quicksort.
/// 
/// Type of array element.
public abstract class QuickSorter : IComparisonSorter
{
    /// 
    ///     Sorts array using Hoare partition scheme,
    ///     internal, in-place,
    ///     time complexity average: O(n log(n)),
    ///     time complexity worst: O(n^2),
    ///     space complexity: O(log(n)),
    ///     where n - array length.
    /// 
    /// Array to sort.
    /// Compares elements.
    public void Sort(T[] array, IComparer comparer) => Sort(array, comparer, 0, array.Length - 1);

    protected abstract T SelectPivot(T[] array, IComparer comparer, int left, int right);

    private void Sort(T[] array, IComparer comparer, int left, int right)
    {
        if (left >= right)
        {
            return;
        }

        var p = Partition(array, comparer, left, right);
        Sort(array, comparer, left, p);
        Sort(array, comparer, p + 1, right);
    }

    private int Partition(T[] array, IComparer comparer, int left, int right)
    {
        var pivot = SelectPivot(array, comparer, left, right);
        var nleft = left;
        var nright = right;
        while (true)
        {
            while (comparer.Compare(array[nleft], pivot)  0)
            {
                nright--;
            }

            if (nleft >= nright)
            {
                return nright;
            }

            var t = array[nleft];
            array[nleft] = array[nright];
            array[nright] = t;

            nleft++;
            nright--;
        }
    }
}

线性搜索

/// 
///     Class that implements linear search algorithm.
/// 
/// Type of array element.
public class LinearSearcher
{
    /// 
    ///     Finds first item in array that satisfies specified term
    ///     Time complexity: O(n)
    ///     Space complexity: O(1).
    /// 
    /// Array to search in.
    /// Term to check against.
    /// First item that satisfies term.
    public T Find(T[] data, Func term)
    {
        for (var i = 0; i < data.Length; i++)
        {
            if (term(data[i]))
            {
                return data[i];
            }
        }

        throw new ItemNotFoundException();
    }

    /// 
    ///     Finds index of first item in array that satisfies specified term
    ///     Time complexity: O(n)
    ///     Space complexity: O(1).
    /// 
    /// Array to search in.
    /// Term to check against.
    /// Index of first item that satisfies term or -1 if none found.
    public int FindIndex(T[] data, Func term)
    {
        for (var i = 0; i < data.Length; i++)
        {
            if (term(data[i]))
            {
                return i;
            }
        }

        return -1;
    }
}

项目源码地址

更多项目实用功能和特性欢迎前往项目开源地址查看👀，别忘了给项目一个Star支持💖。

GitHub开源地址：https://github.com/TheAlgorithms/C-Sharp