c - 许多查找的最佳排序算法

Question

我需要一些建议来选择排序算法来为这个问题编写代码。

在第一阶段，程序将从数据库中获取客户端 ID 和相应的哈希值(可能会使用结构)。可以有 0 条或数千条记录。

在第二阶段，程序将使用从 XML 文件中读取的记录来完成此集合。我已经构建了流解析器。 XML 文件在发票数据之前依次包含所有客户信息。

第二阶段完成后，程序将读取发票数据。对于每张发票，都有一个 clientID，这必须从一组客户中进行检查。发票数量可达百万条记录。

我最初的想法。由于我不知道会有多少客户记录，所以我必须使用链表动态添加内存。在第二阶段结束时，我可以创建一个按 clientID 排序的数据数组，以便我可以执行进一步的搜索，每个发票一个，可以快速检索，可能使用二进制搜索。

我想知道您对我处理这种情况有何建议。我应该使用什么排序算法？ (我将在 C 中编码)。

Answer 1

可以说，最好的算法是满足以下条件的算法:

• 您不必编写任何代码
• 您不会招致任何第三方依赖
• 速度足够快

鉴于几千条记录基本没有，我建议使用qsort对于排序，bsearch用于搜索；这两个都在 C 标准库中。

注意事项:

• qsort 不能用于链表。我强烈建议将您的数据存储在动态增长的数组中；创建的摊销成本是相同的，并且您将获得其他好处(例如，更少的内存开销，更好的 locality of reference )。

• 如果在仔 segmentation 析之后，您发现 bsearch 不够快，那么您可能想转向基于哈希表的查找，因为这是 O(1)，不是 O(log N)。但是，不要尝试自己编写；为此使用现有的库。 (请在此处查看其他答案以获取建议。)