一個開源且全面的C#演算法實戰教程

前言

演算法在電腦科學和程式設計中扮演著至關重要的角色，如在解決問題、最佳化效率、決策最佳化、實作電腦程式、提高可靠性以及促進科學融合等方面具有廣泛而深遠的影響。今天大姚給大家分享一個開源、免費、全面的C#演算法實戰教程： TheAlgorithms/C-Sharp 。

計畫介紹

一個C#實作的各種演算法集合，這些演算法涵蓋了電腦科學、數學和統計學、數據科學、機器學習、工程等多個領域。這些實作及其相關文件旨在為教育工作者和學生提供學習資源。因此，可能會找到針對同一目標使用不同演算法策略和最佳化的多種實作。

計畫原始碼

主要演算法包括

插入排序

/// <summary>
/// class that implements insertion sort algorithm.
/// </summary>
/// <typeparam name="T">Type of array element.</typeparam>
public class InsertionSorter<T> : IComparisonSorter<T>
{
/// <summary>
/// Sorts array using specified comparer,
/// internal, in-place, stable,
/// time complexity: O(n^2),
/// space complexity: O(1),
/// where n - array length.
/// </summary>
/// <param name="array">Array to sort.</param>
/// <param name="comparer">Compares elements.</param>
public void Sort(T[] array, IComparer<T> 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;
}
}
}
}


快速排序

/// <summary>
/// Sorts arrays using quicksort.
/// </summary>
/// <typeparam name="T">Type of array element.</typeparam>
public abstract class QuickSorter<T> : IComparisonSorter<T>
{
/// <summary>
/// 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.
/// </summary>
/// <param name="array">Array to sort.</param>
/// <param name="comparer">Compares elements.</param>
public void Sort(T[] array, IComparer<T> comparer) => Sort(array, comparer, 0, array.Length - 1);
protected abstract T SelectPivot(T[] array, IComparer<T> comparer, int left, int right);
private void Sort(T[] array, IComparer<T> 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<T> 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--;
}
}
}








線性搜尋

/// <summary>
/// class that implements linear search algorithm.
/// </summary>
/// <typeparam name="T">Type of array element.</typeparam>
public class LinearSearcher<T>
{
/// <summary>
/// Finds first item in array that satisfies specified term
/// Time complexity: O(n)
/// Space complexity: O(1).
/// </summary>
/// <param name="data">Array to search in.</param>
/// <param name="term">Term to check against.</param>
/// <returns>First item that satisfies term.</returns>
public T Find(T[] data, Func<T, bool> term)
{
for (var i = 0; i < data.Length; i++)
{
if (term(data[i]))
{
return data[i];
}
}
throw new ItemNotFoundException();
}
/// <summary>
/// Finds index of first item in array that satisfies specified term
/// Time complexity: O(n)
/// Space complexity: O(1).
/// </summary>
/// <param name="data">Array to search in.</param>
/// <param name="term">Term to check against.</param>
/// <returns>Index of first item that satisfies term or -1 if none found.</returns>
public int FindIndex(T[] data, Func<T, bool> 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