C#实战：从零搭建100+算法与数据结构库的完整指南

简介：这是一套面向C#开发者和算法学习者的高级算法与数据结构源码合集，围绕100多种常见算法展开，覆盖AVL树、红黑树、B+树、B树、区间树、R树、四叉树、配对堆、斐波那契堆、treap、伸展树等经典实现。资源既适合用于复习数据结构原理，也适合在.NET Standard 1.0或.NET Framework 4.0及以上环境中直接参考、改造或集成。压缩包共558个文件，以258个cs源码文件为核心，辅以247个html文档、工程配置文件和少量脚本，整体大小仅3.01MB，目录结构清晰便于按项目查找。已有206人浏览学习，对希望通过实际代码理解算法细节的读者有较好参考价值。从目录结构可以看到项目包含B+树、红黑树、AVL树、区间树等算法的完整原始实现，同时附有构建脚本与NuGet配置，方便本地还原、编译和进一步扩展。

1. 在C#里实现100多种算法和数据结构：这不是重复造轮子，而是补上最后一公里

某开发者在处理一个后台查询接口时，发现列表里存了上万条记录，每次按某个字段定位数据都靠线性扫描，接口从200毫秒一路涨到2秒。他翻遍NuGet上的算法包，要么只覆盖排序，要么不开源，要么不能直接处理自定义对象。最后他决定自己维护一套覆盖排序、查找、树与图、动态规划等100多种经典算法与数据结构的C#实现，把老接口换掉之后，单个查询掉到个位数毫秒。这件事听起来像重复造轮子，但在实际项目里，内置集合和零散算法包之间往往缺一个“可按自己规则改、可单步调试、可度量性能”的中间层。本文把这套库的搭建思路拆开：怎么分类、怎么写、哪些坑必须绕开，以及你到底需不需要自己维护一份。

2. C#算法库的骨架：先想清楚这100多种实现为什么值得亲自写

2.1 值类型、引用类型与GC：C#实现算法绕不开的三座山

很多人从C或Java转过来写C#算法时，第一反应是“语言都差不多，翻译一遍就行”。实际动手后发现完全不同。C#里有值类型和引用类型的严格区分：一个int在数组里是连续排布的4字节，一个class数组里存的是引用，真正的对象散落在托管堆上。排序算法交换两个元素时，前者是内存块的整体拷贝，后者只是指针变更，代价差一个数量级。

更隐蔽的是GC压力。手写链表时每插入一个节点就是一个堆分配，当数据量达到百万级，GC的回收频次会直接影响接口延迟。我一般会把“分配次数”作为算法选型的重要指标：能用数组连续内存的，不用链式结构；能用struct承载的中间状态的，尽量不用class。这也是为什么这套实现里大量使用泛型约束和ref返回，而不是像早期教程那样用object塞满所有位置。

另一个关键点在比较操作。C#里实现泛型算法时，约束写成where T : IComparable<T>和写成where T : IComparer<T>，性能表现完全不同。前者在值类型上走的是直接接口调用，后者需要包装一层比较器对象。我的习惯是库内部统一使用Comparer<T>.Default，这样既能在值类型上获得接近零开销的路径，又给外部调用者留出注入自定义比较规则的口子，后面所有排序和查找算法都从这条路径走。

2.2 100多种算法怎么分类：从排序查找到字符串与数学的六块拼图

要维护一个上百个算法的库，第一步不是写代码，而是分类。分类决定使用者找不找得到、改不改得动。我实际搭库时把算法分成六类：排序与查找、线性数据结构、树与图、动态规划与贪心、字符串处理、数学与位运算。每一类在源码里对应一个独立目录，目录下每个算法一个文件，文件名就是算法名，比如QuickSort.cs、BinarySearch.cs、RedBlackTree.cs。

排序与查找是最大的入口，堆排序、归并排序、快速排序、二分查找全部收纳。线性数据结构包括单向链表、栈、队列、循环缓冲。树与图这一类最杂，二叉搜索树、AVL、线段树、图的BFS/DFS、最短路径都会放进来，其中和“剪枝算法”相关的回溯框架也归在动态规划那一组。字符串处理有KMP、Trie树这类高频需求，数学与位运算则收集了素数筛、最大公约数一类的基础工具，有些冷门但精妙的算法也会单独开一个小目录，按需查阅。

这样分类有个直接好处：热门的排序、查找、数据结构排序算法、归并排序算法这类诉求，使用者能一步到位翻到对应文件。同时每类拥有自己的README，写明适用场景和复杂度，避免别人把AVL和二叉搜索树搞混。我建议维护这类库的人，都先画一张分类表再动手写代码，不然一百个文件堆在一起，三个月后连自己都要翻半天。

2.3 通用骨架与验证入口：让每个算法都长同一个样子

实现一百多个算法时，最怕每个文件一套风格。有的方法叫Sort，有的叫sort，有的返回void，有的返回数组，调用者根本记不住。我在写之前定了一个统一契约：所有纯函数算法都用静态方法；所有有状态的容器都用类实现；输入参数统一放前面，配置参数（如比较器）放最后；能用已有输入直接返回结果的就不维护内部状态。

下面这个辅助方法展示了这套库的通用写法。它用来快速验证排序结果是否正确，几乎所有排序算法完成后第一件事就是调用它。

public static class AlgorithmHelpers { // 验证数组是否非降序排列，是所有排序算法的公共检查入口 public static bool IsSorted<T>(T[] data, IComparer<T> comparer = null) { if (data == null || data.Length < 2) { return true; } comparer ??= Comparer<T>.Default; for (int i = 1; i < data.Length; i++) { // 只要前一个元素大于后一个，就说明排序被破坏了 if (comparer.Compare(data[i - 1], data[i]) > 0) { return false; } } return true; } }

逻辑很简单，却体现了整套库的两个约定：参数T是泛型，被约束为可使用Comparer<T>.Default；比较器为空时自动回退到默认规则，调用方不需要每次都传。参数说明里，data是要检查的数组，允许为空数组，返回true；comparer是可选比较器，传null时使用类型的默认比较规则。注意这里用??=是在C# 8.0之后的语法，如果你的项目还在老版本框架上，要改成普通赋值的写法。

有了这个辅助方法，后续每个排序算法实现完，都可以立刻用一组随机数据自查一遍，不用等集成测试环境。这也是这套库和网上零散代码段最大的区别：它自带验收标准，每个算法文件旁边挂着一个同级测试类，跑一次就知道有没有写对。

3. 排序与查找：把高频算法写成C#风格的泛型实现

3.1 快速排序的C#实现：pivot选择、递归深度与数组区间

快速排序是这套库里被引用最多的算法之一，但大部分教程版本直接照搬教科书，数组长度一到十万且数据接近有序时，递归深度等于数组长度，直接把栈打爆。我在这套实现里选了Lomuto分区，pivot取当前区间最后一个元素，同时把递归深度控制在期望O(log n)。

public static class QuickSort { // 对外入口：对整个数组排序 public static void Sort<T>(T[] array) where T : IComparable<T> { Sort(array, 0, array.Length - 1); } // 重载：支持对数组的指定区间排序，left和right都是闭区间下标 public static void Sort<T>(T[] array, int left, int right) where T : IComparable<T> { while (left < right) { int pivot = Partition(array, left, right); // 递归排序左半部分 Sort(array, left, pivot - 1); // 尾递归优化：将下次循环的区间设为右半部分，而不是再压一层栈 left = pivot + 1; } } private static int Partition<T>(T[] array, int left, int right) where T : IComparable<T> { // 取右端元素作为pivot，单次遍历将数组分成小于和大于等于两半 T pivotValue = array[right]; int storeIndex = left; for (int i = left; i < right; i++) { if (array[i].CompareTo(pivotValue) < 0) { Swap(array, i, storeIndex); storeIndex++; } } // 把pivot放到最终位置，返回该位置下标 Swap(array, storeIndex, right); return storeIndex; } private static void Swap<T>(T[] array, int i, int j) { (array[i], array[j]) = (array[j], array[i]); } }

Sort入口有两个重载，第一版保证调用方不用记下标，第二版为需要局部排序的场景开放区间参数。Partition方法每执行一轮，pivot必定落在它最终有序时的位置，左边全小于它，右边全大于等于它。代码里用了一个替换式尾递归优化：只递归左半段，右半段交给下一次while循环继续处理，这样最坏情况下递归深度也变成O(log n)，十万级数组在默认栈大小下可以安全跑完。元组交换是C# 7.0之后的语法，老项目要拆成三行临时变量。

这套实现的代价是：对接近有序的数组，因为pivot总是取最后一个元素，分区会非常不均匀。实际项目中如果高频处理近似有序数据，我建议在进入Sort前先随机洗一次数组，或者把pivot改成“取左中右三者的中位数”，后者在AlgorithmLibrary里单独有一个QuickSortWithMedianOfThree版本可供替换。

3.2 二分查找：左闭右闭的边界约定与找不到时的返回语义

二分查找是数据结构折半查找例题里的常客，但写对边界比大多数人想的难。我这个实现采用左闭右闭区间[left, right]，终止条件是left > right，返回值统一为：找到时返回下标，找不到时返回-1。这个约定和C#内置的Array.BinarySearch保持一致，调用者不会混淆。

public static class BinarySearch { // 在有序数组中查找target，找到返回下标，找不到返回-1 public static int Search<T>(T[] array, T target) where T : IComparable<T> { int left = 0; int right = array.Length - 1; while (left <= right) { // 用减法避免(left + right)溢出，left和right很大时这行是关键 int mid = left + (right - left) / 2; int cmp = array[mid].CompareTo(target); if (cmp == 0) { return mid; } if (cmp < 0) { // array[mid]比target小，目标只可能在右半区 left = mid + 1; } else { // array[mid]比target大，目标只可能在左半区 right = mid - 1; } } return -1; } }

这里最值得留意的是mid = left + (right - left) / 2，上一代C#代码经常直接写(left + right) / 2，当数组长度达到int上限的一半时，加法会溢出成负数，导致死循环。CompareTo返回负数、零、正数三种语义也在这里体现：判断cmp < 0而不是cmp == -1，是因为不同实现可能返回任意负值，只比较符号位置才稳妥。

这个算法要求输入已经有序，库入口处没有做排序检查，因为IsSorted的代价是O(n)，会破坏二分查找O(log n)的意义。调用者需要自行保证前置条件，我在方法注释里写清楚了这一点。如果你需要“找到第一个不小于target的位置”，即C++的lower_bound语义，可以在返回-1的出口改记left值，这就是扩展版LowerBound方法的由来。

3.3 堆排序算法：从数组建堆到TopK的一次到位

堆排序算法在这套库里除了体现“选择排序的优化版”之外，更多时候被用来提取TopK元素。与快速排序不同，堆排序在最坏情况下稳定在O(n log n)，不需要考虑pivot退化问题。下面实现采用大顶堆，排序结果从小到大。

public static class HeapSort { // 对整个数组原地排序，不需要额外空间 public static void Sort<T>(T[] array) where T : IComparable<T> { int n = array.Length; // 从最后一个非叶子节点开始自底向上建堆 for (int i = n / 2 - 1; i >= 0; i--) { Heapify(array, n, i); } // 每次把堆顶（最大值）换到当前末尾，再对剩余部分重新调整 for (int i = n - 1; i > 0; i--) { Swap(array, 0, i); Heapify(array, i, 0); } } // 对下标为index的节点做下沉操作，heapSize表示当前堆的有效长度 private static void Heapify<T>(T[] array, int heapSize, int index) where T : IComparable<T> { int largest = index; int leftChild = 2 * index + 1; int rightChild = 2 * index + 2; if (leftChild < heapSize && array[leftChild].CompareTo(array[largest]) > 0) { largest = leftChild; } if (rightChild < heapSize && array[rightChild].CompareTo(array[largest]) > 0) { largest = rightChild; } if (largest != index) { Swap(array, largest, index); // 被交换下去的节点可能仍不满足堆性质，继续下沉 Heapify(array, heapSize, largest); } } private static void Swap<T>(T[] array, int i, int j) { (array[i], array[j]) = (array[j], array[i]); } }

建堆阶段从n / 2 - 1开始，是因为完全二叉树里下标大于n/2 - 1的节点全是叶子，不需要下沉。Sort方法第二个循环的结束条件是i > 0，因为当堆里只剩一个元素时它已经有序，不必再处理。Heapify是递归写法，如果数组特别大且担心递归栈，可以改成while循环迭代下沉，这是这套实现与朴素教程版本的一个性能差异点。

实际项目里我更常用的是MaxHeap<T>类，它内部持有这个堆化逻辑，暴露Push和Pop方法，用来从百万级数据中取前100个最大值时，时间稳定在几十毫秒，比完整排序快一个量级。堆排序本身的直接用途偏教学，但堆这个数据结构在高频场景里几乎无处不在，所以我把它的核心实现做成可复用组件，而不是只留一个静态排序方法。

4. 树与哈希表：C#手写数据结构的三个高频案例

4.1 二叉搜索树的插入与包含判断：递归写法与删除节点的坑

二叉搜索树是树结构里最基础的实现。很多开发者以为它很简单，真正用起来才发现：插入和查找好写，删除节点时如果左右子树都存在，要找后继节点来替换，这一步容易写出漏分支的bug。这套库里的BinarySearchTree<T>类完整实现了插入、查找、删除和中序遍历，下面展示核心的插入与查找。

public class BinarySearchTree<T> where T : IComparable<T> { // 节点内部类，携带左右子树引用 private class Node { public T Value; public Node Left; public Node Right; public Node(T value) { Value = value; } } private Node _root; // 对外暴露的插入入口，屏蔽节点递归逻辑 public void Insert(T value) { _root = InsertRecursive(_root, value); } private Node InsertRecursive(Node node, T value) { if (node == null) { return new Node(value); } int cmp = value.CompareTo(node.Value); if (cmp < 0) { // 新值比当前节点小，进左子树 node.Left = InsertRecursive(node.Left, value); } else if (cmp > 0) { // 新值比当前节点大，进右子树 node.Right = InsertRecursive(node.Right, value); } return node; } // 非递归查找，避免查找深度大时产生递归栈压力 public bool Contains(T value) { Node current = _root; while (current != null) { int cmp = value.CompareTo(current.Value); if (cmp == 0) { return true; } current = cmp < 0 ? current.Left : current.Right; } return false; } }

插入用递归是因为它需要把新节点挂到父节点上，递归返回值正好是“处理完的子树根”。每个递归调用都会产生一个栈帧，树不平衡时深度可能等于节点数，所以Contains我特意写成while循环，避免重复递归。值相等时插入方法直接返回原节点，因此这个二叉树不存储重复值；需要支持重复值时，可以在节点上加一个计数或允许右子树存放相等值，两种策略各有取舍，我建议项目里第一版先做不重复模型，后续按需求扩展。

删除节点的动作没有贴全，但这里必须提醒：被删除节点有两个孩子时，标准做法是找到右子树的最小节点，把它的值复制到待删节点，再删掉那个最小节点。这个最小节点最多只有一个右孩子，删除它就退化成“删除单孩子节点”的简单情况。想绕开这个复杂度，简单做法可以给节点加一个bool IsDeleted标记，删除时只打标记，但这样树里会堆大量“已删除”节点，遍历输出时要过滤，不适合长期维护。

4.2 手写单向链表：内存占用比LinkedList 少一半的关键点

C#内置的LinkedList<T>是双向链表，每个节点持有前驱和后继两个引用。如果你的业务只需要顺序遍历和尾部插入，用双向链表意味着每个节点多付出一个引用的内存开销。在百万级节点的场景下，这多出来的8字节乘以百万，直接反映在GC堆的占用上。

我在这套库里放了一个SinglyLinkedList<T>，只保留指向下一个节点的引用，提供AddFirst和Remove两个高频操作，完整代码如下：

public class SinglyLinkedList<T> { private class Node { public T Value; public Node Next; public Node(T value) { Value = value; } } private Node _head; private int _count; public int Count => _count; // 头部插入：新节点指向原头节点，再更新头指针 public void AddFirst(T value) { Node newNode = new Node(value); newNode.Next = _head; _head = newNode; _count++; } // 按值删除第一个匹配节点，删除成功返回true public bool Remove(T value) { Node prev = null; Node current = _head; while (current != null) { if (EqualityComparer<T>.Default.Equals(current.Value, value)) { if (prev == null) { // 删除的是头节点 _head = current.Next; } else { // 跳过当前节点，让上一个节点直接连到下一个 prev.Next = current.Next; } _count--; return true; } prev = current; current = current.Next; } return false; } }

EqualityComparer<T>.Default和排序时的Comparer<T>.Default是同一设计思路，避免对T做硬编码类型判断。Remove操作最麻烦的是维护前驱指针，删除头节点时要特别注意prev == null的分支。这版实现没有提供AddLast的优化指针，尾部插入是O(n)的，如果你的场景以尾部追加为主，应该换成带_tail字段的版本，或者在文件说明里提醒使用者改用内置LinkedList。

这套实现的真实应用场景是内存敏感的大规模事件队列：比如需要保存最近一百万个事件对象，每个对象本身已经占几十字节，双向链表额外多出的一个引用会让GC压力明显上升。换成单向链表再把Node做成内部类，事件处理完就置空头指针，整个队列可以被快速回收。

4.3 开放寻址哈希表：和Dictionary<TKey,TValue>互补的选择

C#内置的Dictionary<TKey,TValue>使用分离链表法处理哈希冲突，每个桶后面挂一个链表或数组，键的分布不均匀时，最坏情况会退化。开放寻址法是另一种思路：冲突发生时不拉链，而是往后探测下一个空位，所有数据都保存在同一个连续数组里，对CPU缓存更友好，也没有链表节点的堆分配。

public class OpenAddressingHashSet<T> where T : class { private T[] _slots; private int _count; private const double LoadFactor = 0.7; public OpenAddressingHashSet(int capacity = 16) { _slots = new T[capacity]; } // 添加元素，已存在时返回false public bool Add(T value) { // 超过负载因子先扩容，避免探测链过长 if (_count >= _slots.Length * LoadFactor) { Resize(); } int index = Math.Abs(value.GetHashCode()) % _slots.Length; // 线性探测：当前坑位被占就继续往后找 while (_slots[index] != null) { if (EqualityComparer<T>.Default.Equals(_slots[index], value)) { return false; } index = (index + 1) % _slots.Length; } _slots[index] = value; _count++; return true; } private void Resize() { T[] old = _slots; _slots = new T[old.Length * 2]; _count = 0; // 重新哈希所有旧元素，容量扩大后下标会变化 foreach (T item in old) { if (item != null) { Add(item); } } } }

这版实现的类约束是where T : class，用null表示空槽位，避免值类型默认值造成的歧义。实际生产版本建议改成Nullable<T>或加一个独立的bool[]占用标记数组。线性探测有个性能细节：负载因子设为0.7，能保证平均探测次数保持低位，超过就扩容翻倍并重新哈希。GetHashCode的结果分布直接决定哈希表表现，如果key的哈希值分布很差，比如全落在同一个桶，线性探测会退化成近乎线性扫描。

内置Dictionary在高并发多线程场景要加锁或用ConcurrentDictionary，而开放寻址版本因为数据集中在一个数组里，配合读写锁做细粒度并发控制时，缓存命中率更高。这是把它收进这套库的原因：不是替代内置容器，而是给特定场景一个可调参数的结构。

5. 避坑记录：C#里实现算法时最容易翻车的5个细节

5.1 结构体数组排序慢得离谱：值类型拷贝与装箱的隐形开销

现象：同样的快速排序代码，把一条条数据从class改成struct后，耗时翻了四倍，GC分配也明显增加，甚至出现“排序结果没变化”的错觉。

原因：结构体是值类型，每次从数组索引器读取都是一次整体拷贝，比较时读一次拷贝一次，交换时又拷贝两次。如果泛型约束里用了IComparable接口作为比较路径，每个int或struct在比较时还会发生装箱，产生临时堆对象。.NET的泛型集合对值类型有特殊优化，但自己手写算法时很容易踩进接口调用的坑。

解决：优先让泛型约束落在IComparable<T>而不是非泛型IComparable；比较操作统一走Comparer<T>.Default；大批量数据尽量使用数组而非List<T>，因为数组索引器在JIT里能获得更好的内联效果。如果你需要调整结构体里的某个字段后再参与比较，用ref或in参数传递，避免拷贝整个结构体。

5.2 快速排序十万级数据栈溢出：递归深度和尾递归优化

现象：对一个基本有序的十万个整数跑快速排序，扑通一声抛出StackOverflowException，程序直接崩。同样的数据在数据量小时却一切正常。

原因：快速排序每次分区后递归处理两侧区间，如果pivot总是选到当前区间的最大值或最小值，一侧为空，另一侧只减少一个元素，递归深度就退化成O(n)。十万个元素压十万层栈，默认1MB栈空间撑不住。

解决：至少做三件事。第一，选pivot时从区间里随机挑一个元素，和末尾元素交换后再分区，避免有序数组的规律性输入造成最坏分区。第二，采用本文3.1节的做法，只递归左半区间，右半区间放到循环里继续处理。第三，小区间阈值判断：当区间长度小于16时改用插入排序，既减少递归层数，在小数据上插入排序也更快。实现后务必跑一次“全有序数组”和“全逆序数组”的回归用例。

5.3 同一次排序两次结果不一样：比较器混乱的玄学问题

现象：同一个数组，第一次用Array.Sort排序结果正常，自己实现的快速排序跑出来顺序不稳定，再跑一次又变了。或者两个字段的大小规则在不同代码路径里定义得不一致，导致排序结果“随缘”。

原因：C#里有IComparable<T>、IComparer<T>、Comparison<T>三种比较载体。如果算法内部用的是类型自带的CompareTo，而调用方传入的是自定义IComparer，两边规则冲突时，排序结果完全取决于哪条路径被触发。更隐蔽的是比较器违反传递性，比如a < b、b < c但c < a，排序算法在这种输入下行为未定义。

解决：库内部统一只认IComparer<T>一个入口，算法方法签名里一律接收IComparer<T>参数，默认值为null时回退到Comparer<T>.Default。所有排序算法完成后，用AlgorithmHelpers.IsSorted过一遍，并且专门写一组传递性测试数据。自定义比较器时，务必保证Compare(a, b) < 0和Compare(b, a) > 0严格匹配。

5.4 泛型写不好就疯狂装箱：明明用的是int却慢如老牛

现象：一个简单的冒泡排序算法，输入一万个int，耗时竟然是Array.Sort的几十倍。调试时发现每次比较都产生一个boxed对象，内存字节里多了大量堆分配。

原因：写签名时图省事用了where T : IComparable（非泛型接口），或者内部把对象转成了object。int实现IComparable时是隐式装箱的，每次CompareTo调用前，int被复制到堆上生成一个对象。这一万次比较就是一万次堆分配，加一万次待回收垃圾。

解决：所有泛型约束从非泛型IComparable换成泛型的IComparable<T>。如果只是为了做示例或教学，可以不用泛型，直接写int版本；一旦要用泛型支撑多种类型，必须确认运行时实际调用的是泛型接口。这里的判断方法很简单：在算法里加一个Type.GetType()日志，看比较对象是int还是boxed的引用类型。另外，用Debugger单步观察时能看到装箱发生时变量类型显示为object。

5.5 基准测试被JIT预热骗了：第一轮永远是最慢的

现象：用Stopwatch测算法性能，第一次调用跑了80毫秒，紧接着再跑一次只剩1.2毫秒。于是得出“这个算法第一次慢是正常的，之后都快”的结论，把第一次数据直接扔掉。这个结论在线上环境可能站不住。

原因：.NET的JIT编译器在方法首次执行前才生成机器码，预热成本、方法内联决策、CPU缓存填充都会让第一次调用明显偏慢。如果每个算法都只测一次，你测到的是JIT编译时间加运行时间的混合体，不是算法本身的稳定吞吐量。

解决：基准测试流程固定为三步。第一步，用一个中等大小的数据跑一遍要测的算法，触发JIT编译和类型初始化；第二步，短暂停顿后开始正式计时；第三步，同一份数据连续跑若干轮，记录后几轮的平均值和中位数，不取最大值也不取最小值。如果要严谨地对比两种实现，两边的预热轮数、数据顺序、GC状态必须保持一致。我一贯的做法是在每个算法类里预留一个静态WarmUp方法，所有性能对比前先调它，这样测出来的数字才具备横向可比性。

6. 进阶用法：给每个算法配验证器和基准测试，再收进项目

6.1 用验证器给所有排序算法当“标准答案”

当库里的算法超过五十个以后，改动一个公共工具方法都可能影响一批实现。我给自己定了一条规矩：任何算法合入库之前，旁边必须有同名验证器。排序算法用IsSorted检查结果顺序；查找算法用“随机生成十万个数据，排序后逐个查找，再用暴力扫描二次确认”的方式比对；树结构则做插入一批值后，中序遍历验证是否升序。

public static void QuickSortValidator() { Random rand = new Random(42); int[] data = new int[100000]; for (int i = 0; i < data.Length; i++) { data[i] = rand.Next(0, 1000000); } QuickSort.Sort(data); // 验证排序结果确实是非降序 if (!AlgorithmHelpers.IsSorted(data)) { throw new InvalidOperationException("快速排序验证失败"); } }

这段代码用固定种子42生成随机数据，保证每次跑出来的用例完全一致，出现问题时可以精确复现。验证器放在AlgorithmLibrary.Tests命名空间下，源码库和测试库分两个工程，正式环境不编译测试代码。

6.2 用数据说话：不同数据规模下的选型表

我通常会在库的README里维护一张性能选型表，列出不同数据量下各算法的耗时区间，表格由基准测试脚本自动生成。下面是一份典型记录（基于某开发者的测试环境，数值仅供参考，机器不同会变化）：

这张表的作用不是比较谁“最好”，而是帮使用者在接入项目前先判断：数据规模要到百万级，堆排序的稳定性才值得它的常数开销；如果数据只有几千条，直接用内置Array.Sort就好。我现在的习惯是，每接一个新数据结构进库，先把这张表的对应行跑出来，再把验证器挂进代码仓库的自动构建流程里。

我自己吃过亏：早期把几十个算法堆进一个静态类，没有统一比较器入口，也没有验证器，结果某个排序被下游调用时传了自定义比较器，因为传递性不满足跑出了错误顺序，排查了整整一下午。从那以后，每个算法必须带验证器，每个比较器接口必须从同一路径走，成了我这套维护流程里最不能省的两道工序。希望帮到你。

本文还有配套的精品资源，点击获取