c - 最容易在C中实现在线排序数据结构

Question

我正在扫描一个大型数据源，目前大约有 800 万个条目，我希望按字母顺序提取每个条目的字符串。

Currenlty 我把它们放在一个数组中，然后使用 qsort() 对它们进行索引排序，效果很好。

但出于好奇，我正在考虑将每个字符串插入一个数据结构中，该数据结构在我从数据源扫描它们时按字母顺序维护它们，部分原因是为了获得实现经验，部分原因是没有它会感觉更快扫描完成后等待排序完成(-:

哪种数据结构最容易用 C 语言实现？

更新

为了澄清，我需要执行的唯一操作是插入一个项目并在完成时转储索引，我的意思是对于原始订单中的每个项目转储一个整数，表示它在排序后的顺序。

总结

• 最容易实现的是二叉搜索树。
• 自平衡二叉树要好得多，但实现起来并不简单。
• 插入可以迭代完成，但用于转储结果的中序遍历和完成后删除树的后序遍历都需要递归或显式堆栈。
• 如果不实现平衡，有序输入的运行将导致退化的最坏情况，即链表。这意味着严重影响插入操作速度的深树。
• 稍微打乱输入可以显着打乱有序输入，并且更容易实现这种平衡。

Answer 1

二叉搜索树。或自平衡搜索树。但是不要指望它们比正确实现的动态数组更快，因为数组比指针结构具有更好的引用局部性。很多。此外，不平衡的 BST 可能会“线性化”，因此您的整个算法变成 O(n²)，就像快速排序一样。