当前位置：首页 > news >正文

WPF框架中常用算法

news 2025/5/1 7:15:00

WPF框架中常用算法与实现

一、排序算法

1. 快速排序 (Quick Sort)

应用场景：大数据集合排序、性能敏感场景

public static void QuickSort(IList<int> list, int left, int right)
{if (left < right){int pivotIndex = Partition(list, left, right);QuickSort(list, left, pivotIndex - 1);QuickSort(list, pivotIndex + 1, right);}
}private static int Partition(IList<int> list, int left, int right)
{int pivot = list[right];int i = left - 1;for (int j = left; j < right; j++){if (list[j] <= pivot){i++;Swap(list, i, j);}}Swap(list, i + 1, right);return i + 1;
}private static void Swap(IList<int> list, int i, int j)
{int temp = list[i];list[i] = list[j];list[j] = temp;
}

WPF中使用示例：

// 在ViewModel中
public void SortData()
{var data = new List<int> { 5, 2, 9, 1, 5, 6 };QuickSort(data, 0, data.Count - 1);// 更新UI绑定集合MyDataCollection = new ObservableCollection<int>(data);
}

2. 归并排序 (Merge Sort)

应用场景：稳定排序需求、外部排序

public static void MergeSort(IList<int> list)
{if (list.Count <= 1) return;int mid = list.Count / 2;var left = list.Take(mid).ToList();var right = list.Skip(mid).ToList();MergeSort(left);MergeSort(right);Merge(list, left, right);
}private static void Merge(IList<int> list, IList<int> left, IList<int> right)
{int i = 0, j = 0, k = 0;while (i < left.Count && j < right.Count){if (left[i] <= right[j])list[k++] = left[i++];elselist[k++] = right[j++];}while (i < left.Count)list[k++] = left[i++];while (j < right.Count)list[k++] = right[j++];
}

二、搜索算法

1. 二分查找 (Binary Search)

应用场景：有序集合快速查找

public static int BinarySearch(IList<int> list, int target)
{int left = 0, right = list.Count - 1;while (left <= right){int mid = left + (right - left) / 2;if (list[mid] == target)return mid;else if (list[mid] < target)left = mid + 1;elseright = mid - 1;}return -1; // 未找到
}

WPF中使用示例：

// 在ViewModel中
public int FindItem(int target)
{var sortedData = MyDataCollection.OrderBy(x => x).ToList();int index = BinarySearch(sortedData, target);if (index >= 0)return sortedData[index];return -1;
}

2. 深度优先搜索 (DFS)

应用场景：树形结构遍历、路径查找

public class TreeNode
{public int Value { get; set; }public List<TreeNode> Children { get; } = new List<TreeNode>();
}public void DFS(TreeNode node, Action<TreeNode> action)
{if (node == null) return;action(node);foreach (var child in node.Children){DFS(child, action);}
}

WPF中使用示例：

// 在ViewModel中
private void TraverseTree()
{var root = GetTreeRoot(); // 获取树根节点DFS(root, node => {// 处理每个节点Debug.WriteLine($"Visited node with value: {node.Value}");});
}

三、图形算法

1. A*寻路算法

应用场景：游戏路径规划、导航系统

public class Node : IComparable<Node>
{public Point Position { get; }public Node Parent { get; set; }public double GCost { get; set; } // 从起点到当前节点的成本public double HCost { get; set; } // 从当前节点到目标的估计成本public double FCost => GCost + HCost;public Node(Point position){Position = position;}public int CompareTo(Node other){return FCost.CompareTo(other.FCost);}
}public List<Point> FindPath(Grid grid, Point start, Point target)
{var openSet = new PriorityQueue<Node>();var closedSet = new HashSet<Point>();var startNode = new Node(start) { GCost = 0, HCost = Heuristic(start, target) };openSet.Enqueue(startNode);while (openSet.Count > 0){var currentNode = openSet.Dequeue();if (currentNode.Position == target)return RetracePath(startNode, currentNode);closedSet.Add(currentNode.Position);foreach (var neighbor in GetNeighbors(grid, currentNode.Position)){if (closedSet.Contains(neighbor))continue;var neighborNode = new Node(neighbor){GCost = currentNode.GCost + 1,HCost = Heuristic(neighbor, target),Parent = currentNode};if (!openSet.Contains(neighborNode) || neighborNode.GCost < GetNodeInOpenSet(openSet, neighbor).GCost){openSet.Enqueue(neighborNode);}}}return null; // 无路径
}private double Heuristic(Point a, Point b)
{return Math.Abs(a.X - b.X) + Math.Abs(a.Y - b.Y); // 曼哈顿距离
}private List<Point> RetracePath(Node startNode, Node endNode)
{var path = new List<Point>();var currentNode = endNode;while (currentNode != startNode){path.Add(currentNode.Position);currentNode = currentNode.Parent;}path.Reverse();return path;
}

WPF中使用示例：

// 在游戏ViewModel中
private List<Point> CalculatePath(Point start, Point target)
{var grid = GameGrid; // 游戏网格var path = Pathfinding.FindPath(grid, start, target);// 更新UI显示路径PathVisualization = new ObservableCollection<Point>(path);return path;
}

2. 力导向布局算法

应用场景：关系图可视化、社交网络图

public class ForceDirectedLayout
{private const double Repulsion = 1000;private const double SpringLength = 50;private const double SpringConstant = 0.1;private const double Damping = 0.9;public void UpdatePositions(List<Node> nodes, List<Edge> edges, double deltaTime){// 计算斥力foreach (var node1 in nodes){node1.Velocity = new Vector(0, 0);foreach (var node2 in nodes){if (node1 == node2) continue;var delta = node2.Position - node1.Position;var distance = delta.Length;if (distance > 0){var force = Repulsion / (distance * distance);node1.Velocity += delta.Normalize() * force / node1.Mass;}}}// 计算弹簧力foreach (var edge in edges){var delta = edge.To.Position - edge.From.Position;var distance = delta.Length;var displacement = (distance - SpringLength) * SpringConstant;edge.From.Velocity -= delta.Normalize() * displacement / edge.From.Mass;edge.To.Velocity += delta.Normalize() * displacement / edge.To.Mass;}// 更新位置foreach (var node in nodes){node.Velocity *= Damping;node.Position += node.Velocity * deltaTime;// 边界检查node.Position = new Point(Math.Max(0, Math.Min(node.Position.X, LayoutWidth)),Math.Max(0, Math.Min(node.Position.Y, LayoutHeight)));}}
}

WPF中使用示例：

// 在图表ViewModel中
private void StartLayoutAnimation()
{var layout = new ForceDirectedLayout();var timer = new DispatcherTimer(TimeSpan.FromMilliseconds(16), DispatcherPriority.Render, (s, e) => UpdateLayout(layout), Dispatcher);timer.Start();
}private void UpdateLayout(ForceDirectedLayout layout)
{layout.UpdatePositions(Nodes, Edges, 0.016); // 约60FPS// 更新UI绑定OnPropertyChanged(nameof(Nodes));OnPropertyChanged(nameof(Edges));
}

四、数据结构算法

1. 前缀树(Trie)实现

应用场景：自动补全、拼写检查

public class TrieNode
{public Dictionary<char, TrieNode> Children { get; } = new Dictionary<char, TrieNode>();public bool IsEndOfWord { get; set; }
}public class Trie
{private readonly TrieNode _root = new TrieNode();public void Insert(string word){var node = _root;foreach (var c in word){if (!node.Children.ContainsKey(c))node.Children[c] = new TrieNode();node = node.Children[c];}node.IsEndOfWord = true;}public bool Search(string word){var node = SearchPrefix(word);return node != null && node.IsEndOfWord;}public bool StartsWith(string prefix){return SearchPrefix(prefix) != null;}private TrieNode SearchPrefix(string prefix){var node = _root;foreach (var c in prefix){if (!node.Children.TryGetValue(c, out node))return null;}return node;}
}

WPF中使用示例：

// 在搜索ViewModel中
private Trie _trie = new Trie();public void BuildDictionary(IEnumerable<string> words)
{foreach (var word in words){_trie.Insert(word.ToLower());}
}public IEnumerable<string> GetSuggestions(string prefix)
{var suggestions = new List<string>();var node = _trie.SearchPrefix(prefix.ToLower());if (node != null){CollectWords(node, prefix, suggestions);}return suggestions;
}private void CollectWords(TrieNode node, string prefix, List<string> suggestions)
{if (node.IsEndOfWord)suggestions.Add(prefix);foreach (var kvp in node.Children){CollectWords(kvp.Value, prefix + kvp.Key, suggestions);}
}

2. 并查集(Disjoint Set Union)

应用场景：连通性检测、最小生成树

public class DisjointSet
{private readonly int[] _parent;private readonly int[] _rank;public DisjointSet(int size){_parent = Enumerable.Range(0, size).ToArray();_rank = new int[size];}public int Find(int x){if (_parent[x] != x){_parent[x] = Find(_parent[x]); // 路径压缩}return _parent[x];}public void Union(int x, int y){int rootX = Find(x);int rootY = Find(y);if (rootX != rootY){// 按秩合并if (_rank[rootX] > _rank[rootY])_parent[rootY] = rootX;else if (_rank[rootX] < _rank[rootY])_parent[rootX] = rootY;else{_parent[rootY] = rootX;_rank[rootX]++;}}}
}

WPF中使用示例：

// 在图形编辑ViewModel中
private DisjointSet _dsu;public void InitializeGraph(int nodeCount)
{_dsu = new DisjointSet(nodeCount);
}public void ConnectNodes(int node1, int node2)
{_dsu.Union(node1, node2);// 更新连接可视化UpdateConnections();
}public bool AreConnected(int node1, int node2)
{return _dsu.Find(node1) == _dsu.Find(node2);
}