我需要一些建议来选择一种排序算法来为这个问题编码。
在第一阶段，程序将从数据库中获取客户端 ID 和相应的哈希（可能会使用结构）。可能有 0 条或数千条记录。
在第二阶段，程序将使用从 XML 文件中读取的记录来完成该集合。我已经构建了流解析器。XML 文件在发票数据之前依次包含所有客户信息。
第二阶段完成后，程序将读取发票数据。对于每张发票，都有一个 clientID，这必须从一组客户中进行检查。发票的数量可以是数百万条记录。
我最初的想法。由于我不知道会有多少客户记录，我必须使用链表动态添加内存。在第二阶段结束时，我可以创建一个按 clientID 排序的数据数组，以便我可以执行进一步的搜索，每个发票一个，可以快速检索，也许使用二分搜索。
我想知道你建议我如何处理这种情况。我应该使用什么排序算法？（我将使用 C 进行编码）。
可以说，最好的算法是满足以下标准的算法：
鉴于数千条记录基本上没有，我建议qsort用于排序和bsearch搜索；这两个都在 C 标准库中。
需要注意的问题：
qsort不能在链表上使用。我强烈建议将您的数据存储在动态增长的数组中；创建的摊销成本是相同的，并且您将获得其他好处（例如更少的内存开销，更好的引用局部性）。
如果在仔细分析之后，您发现bsearch速度不够快，那么您可能希望转到基于哈希表的查找，因为这是 O(1)，而不是 O(log N)。但是，不要尝试自己编写；为此使用现有的库。（有关建议，请参阅此处的其他答案。）
该glib库包括一个哈希表实现。虽然未排序，但哈希表可以让您进行 O(1) 或恒定时间查找，如果您要查找数百万张发票，这将非常有用。
还有其他可能性，例如Client通过它进行二进制搜索的结构排序数组。假设您的Client结构包含一个unsigned int名为clientID. 如果您的客户 ID 是唯一的且单调递增（不一定等同于数组索引，而是递增），并且您有n记录，那么您只需转到数据透视索引floor(n/2)并查看您的感兴趣 IDi大于、等于或小于枢轴索引处的结构引用所引用的 ID，以便决定接下来要查看数组的哪一半。您的新枢轴索引将是该子数组下限和上限的中点，您将递归搜索，直到找到您感兴趣的元素。
通过排序数组进行二分查找的查找性能为 O(log n) — 比哈希表慢，并且排序数组的成本不为零，但总体内存开销可以更小。如果你有足够的内存，哈希表可能会更快，因此对于大量查找来说通常是一个很好的结构。