作为一个程序员从普通的码农做到中高层管理人员,没有人可以不掌握算法。算法是解决问题的一个有力工具，它通过相关数据结构的使用或者执行，来解决各种复杂问题。在软件开发中，设计和实现高效的算法可以极大地提高应用程序的性能和可靠性，使程序在处理大量数据和用户输入时快速而稳定地工作。本文推荐10 个 C# 最流行和最有用的算法。
1 冒泡排序
冒泡排序是一种简单的排序算法，它通过多次交换相邻元素来排序一个数组。以下是C#代码：
public 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 快速排序
快速排序是一种常用的排序算法：
public void QuickSort ( int [] arr, int low, int high) { if (low high) { int pivotIndex = Partition(arr, low, high); QuickSort(arr, low, pivotIndex - 1 ); QuickSort(arr, pivotIndex + 1 , high); }} public int Partition ( int [] arr, int low, int high) { int pivotValue = arr[high]; int i = low; for ( int j = low; j high; ++j) { if (arr[j] pivotValue) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; ++i; } } int temp1 = arr[i]; arr[i] = arr[high]; arr[high] = temp1; return i;}
3 **排序
**排序是一种简单的排序算法
public void InsertionSort ( int [] arr) { int n = arr.Length; for ( int i = 1 ; i n; ++i) { int key = arr[i]; int j = i - 1 ; while (j = 0 && arr[j] key) { arr[j + 1 ] = arr[j]; --j; } arr[j + 1 ] = key; }}
4选择排序
选择排序是一种简单的排序算法
public void SelectionSort ( int [] arr) { int n = arr.Length; for ( int i = 0 ; i n - 1 ; ++i) { int minIndex = i; for ( int j = i + 1 ; j n; ++j) { if (arr[j] arr[minIndex]) { minIndex = j; } } int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; }}
5 归并排序
归并排序是一种常用的排序算法，它通过将数组分成较小的子问题，排序并合并子数组来排序一个数组。
具体实现步骤:
- 将数组分成两个子数组，直到子数组的大小为1。
- 对每个子数组进行排序，可以使用递归或迭代来排序子数组。
- 将排好序的子数组合并成一个完整的数组。
public void MergeSort ( int [] arr, int left, int right) { if (left right) { int middle = (left + right) / 2 ; MergeSort(arr, left, middle); MergeSort(arr, middle + 1 , right); Merge(arr, left, middle, right); }} public void Merge ( int [] arr, int left, int middle, int right) { int n1 = middle - left + 1 ; int n2 = right - middle; int [] leftArr = new int [n1]; int [] rightArr = new int [n2]; for ( int i = 0 ; i n1; ++i) { leftArr[i] = arr[left + i]; } for ( int i = 0 ; i n2; ++i) { rightArr[i] = arr[middle + i + 1 ]; } int j = 0 ; int k = left; while (j n1 && k = right) { if (leftArr[j] = rightArr[k]) { arr[k] = leftArr[j]; ++j; } else { arr[k] = rightArr[k]; ++k; } } while (j n1) { arr[k] = leftArr[j]; ++j; ++k; } while (k = right) { arr[k] = rightArr[k]; ++k; }}
6 二分查找
二分查找是一种查找算法，它通过重复地将数组划分为两个部分来查找一个特定元素
public int BinarySearch (int[] arr, int x){ int left = 0 ; int right = arr. Length - 1 ; while ( left = right ) { int middle = ( left + right ) / 2 ; if (arr[middle] == x) { return middle; } else if (arr[middle] x) { left = middle + 1 ; } else { right = middle - 1 ; } } return - 1 ;}
7 广度优先搜索
广度优先搜索是一种常用的搜索算法，它通过从给定的起始点开始搜索，扩展所有可达的节点来查找路径或解决问题
public class Node { public int Value { get; set ; } public ListNode Children { get; set ; }} public void BFS (Node node) { QueueNode queue = new QueueNode(); HashSetNode visited = new HashSetNode(); queue .Enqueue(node); visited.Add(node); while ( queue .Count 0 ) { Node current = queue .Dequeue(); Console.WriteLine(current.Value); foreach (Node child in current.Children) { if (!visited.Contains(child)) { visited.Add(child); queue .Enqueue(child); } } }}
8 深度优先搜索
深度优先搜索是一种常用的搜索算法，它通过从给定的起始点开始搜索，沿着一条路径直到无法继续，然后回溯到最近的可达节点并继续搜索
public class Node { public int Value { get ; set ; } public ListNode Children { get ; set ; }} public void DFS ( Node node, HashSetNode visited ) { if (visited.Contains(node)) return ; Console.WriteLine(node.Value); visited.Add(node); foreach (Node child in node.Children) { DFS(child, visited); }}
9 动态规划
动态规划是一种常用的算法思想，它通过将复杂问题分解成更简单的子问题来解决问题。它通常用于优化问题，例如最长公共子序列、最大子数组和背包等问题。 如计算斐波那契数列
public int Fibonacci ( int n) { if (n = 1 ) { return n; } int [] memo = new int [n + 1 ]; memo[ 0 ] = 0 ; memo[ 1 ] = 1 ; for ( int i = 2 ; i = n; i++) { memo[i] = memo[i - 1 ] + memo[i - 2 ]; } return memo[n];}
10 雪花算法
雪花算法是一种常见的唯一 ID 生成算法。它是基于时间戳和机器节点生成的全局唯一 ID，适用于分布式系统中的多台机器.
public class SnowflakeIdGenerator { // 0 41 51 64 // +-------------+------+------------+ // | timestamp | node | sequence | // +-------------+------+------------+ private const long Epoch = 1609459200000L ; // 2021-01-01 的时间戳，可以替换为任何过去的日期 private long NodeId { get ; } private int Sequence { get ; set ; } private long LastTimestamp { get ; set ; } = -1 ; private static readonly object _lock = new object (); public SnowflakeIdGenerator ( long nodeId ) { if (nodeId 0 || nodeId 1023 ) { throw new ArgumentException( "NodeId must be between 0 and 1023." ); } NodeId = nodeId; } public long NextId ( ) { lock (_lock) { long timestamp = GetTimestamp(); if (timestamp LastTimestamp) { throw new Exception( "Clock moved backwards. Refusing to generate id." ); } if (timestamp == LastTimestamp) { Sequence = (Sequence + 1 ) & 4095 ; if (Sequence == 0 ) { timestamp = WaitForNextMillis(LastTimestamp); } } else { Sequence = 0 ; } LastTimestamp = timestamp; return (timestamp - Epoch) 22 | NodeId 12 | Sequence; } } private static long GetTimestamp ( ) { return DateTimeOffset.UtcNow.ToUnixTimeMilliseconds(); } private static long WaitForNextMillis ( long currentTimestamp ) { long timestamp = GetTimestamp(); while (timestamp = currentTimestamp) { timestamp = GetTimestamp(); } return timestamp; }}
