c - 如果数据大部分是排序的，我应该使用哪种数据结构？

Question

我有大量数据（主要是 long long 类型），这些数据大多是排序的（数据分布在不同的文件中，每个文件中的数据都是排序格式）。我需要以排序方式将此数据转储到文件中。我应该使用哪种数据结构。我正在考虑 BST。

我应该使用任何其他 DS 可以为我提供最佳性能吗？

谢谢阿皮特

Answer 1

使用任何额外的数据结构都无济于事。由于您的大部分数据已经排序，您只需要修复偶尔的值，使用一个简单的数组来提取数据，然后使用插入排序。

对于大多数预排序的数据，插入排序在O(n)中运行。

但是，这取决于您是否可以在内存中保存足够大的数组，具体取决于您的输入大小。

更新：

我对您对“大部分排序”的定义不是很清楚。通常这意味着只有少数元素不在精确的排序位置。

但是，正如您进一步所述，“数据位于每个文件单独排序的不同文件中”，那么它可能是子函数调用的一个很好的候选者 - Merge as in merge Sort。

请注意，合并例程合并两个已排序的数组。如果您说 10 个文件，其中每个文件肯定都单独排序，那么使用 Merge 例程只需要 O(n)。

但是，如果您甚至有几个单独的文件没有完美排序（单独）的实例，则需要使用插入排序。

更新 2：

OP 说他不能使用数组，因为他无法提前知道记录的数量。使用简单的链接列表是没有问题的，因为它在时间复杂度上永远不会与数组（顺序访问时间与随机访问时间）竞争。

在评论中指出，如果文件单独排序并且您需要在它们上运行的只是合并过程，则使用链接列表是一个好主意。

如果他可以在某个时候预测大小，那么动态分配的数组是最好的。由于使用了 c++ 标记（仅在后者中删除），因此使用矢量将是一个好主意，因为它可以舒适地调整大小。

否则，一个选项可能是Heap Sort，因为它会首先调用 heapify ，即构建一个堆（因此它可以动态地容纳所需的许多元素）并且仍然产生 O(nlogn)复杂度。这仍然比尝试使用链接列表要好。

Answer 2

也许您根本不需要数据结构。

如果文件已经排序，则可以使用归并排序的合并部分，即 O(n)，或更一般的 O(n*log k)，其中 k 是文件数。

Answer 3

您必须合并多少个文件？

如果只有几个（大约十几个）并且每个单独的文件都已完全排序，那么您根本不需要构建任何类型的复杂数据结构：只需打开所有输入文件，阅读下一个从每个文件中记录，比较，将最小的写入目标，然后从相应的文件中替换该记录。

如果每个文件没有完全排序或者一次打开的文件太多，那么是的，您需要在内存中构建一个中间数据结构。我推荐一个自平衡树，但由于数据已经大部分排序，你几乎每次插入都会重新平衡。堆可能更适合您的目的。

Answer 4

最佳排序算法：

插入排序可以有效地用于几乎排序的数据（O(n) 时间复杂度）。

最佳数据结构：

如果您使用插入排序对其进行排序，则链表是数据结构的最佳选择。

使用链表的原因：

当元素存储为链表时，可以更快地删除和插入元素。