项目介绍
一个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 < array.Length; i++)
{
for (var j = i; j > 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)
{
nleft++;
}
while (comparer.Compare(array[nright], 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
