c# - 找到确切的位置然后插入或添加然后排序？哪个更好？

Question

我们有一个超过 1000 个项目的大列表，其中包含大类（相同类型）。该列表的插入或删除非常频繁。一次插入大约 10 或 20、30 个项目。对于每个项目，我使用快速搜索算法找到要插入的确切位置。但是我想知道如果我将每个项目都添加到列表的末尾然后使用 List.Sort 进行排序（我相信 MS 使用快速排序算法）那么它会更好：消耗更少的 CPU 像当前的？我正在使用 C#、.Net Framework 2.0。

Answer 1

这类问题很少有一个通用的答案。这在很大程度上取决于您的情况。但这是您提出的两个选择之间的中间建议：

对要插入的项目列表进行排序（这需要根据您的描述对 10 - 30 个项目进行排序）。然后，按顺序插入这些。请注意，一旦您找到插入第一项的位置，插入第二项的位置必须严格在该位置之后（依此类推，对于每个后续项），因此您无需再次从头开始搜索. 在这种情况下，只需要搜索插入的列表，因为它会在每次插入后保持其顺序。