我在做一个大型项目，这里就不费心总结了，但是这部分项目是取一个非常大的文本文档（最少50,000字左右（不是唯一的）），并输出每个唯一的单词按最常用到最少使用的顺序排列（前三名可能是“a”、“an”和“the”）。
我的问题当然是，最好的排序算法是什么？我正在阅读计数排序，我喜欢它，但我担心与唯一单词的数量相比，值的范围会太大。
有什么建议么？
问问题
21369 次
9 回答
14
首先，您将需要一个单词图 -> 计数。50,000 个单词并不多——它很容易被记忆，所以没有什么好担心的。在 C++ 中，您可以使用标准的 STL std::map。
然后，一旦有了地图，就可以将所有地图键复制到向量中。
然后，使用自定义比较运算符对该向量进行排序：而不是比较单词，而是比较地图中的计数。（不用担心具体的排序算法——你的数组不是那么大，所以任何标准库排序都适合你。）
于 2009-06-05T03:58:54.653 回答
3
我会从快速排序开始，然后从那里开始。
不过，请查看有关排序算法的 wiki 页面以了解差异。
于 2009-06-05T03:41:40.007 回答
1
看看链接。关于不同算法如何工作的图示。这会给你一个提示！
于 2009-06-05T03:49:00.020 回答
1
假设如果两个单词出现相同的次数，那么对于这个特定问题，您可以获得比快速排序更好的性能，那么输出它们的顺序无关紧要。
第一步：创建一个哈希映射，其中单词作为键值，频率作为关联值。您将在解析文件时填写此哈希映射。执行此操作时，请确保跟踪遇到的最高频率。这一步是 O(n) 复杂度。
第二步：创建一个条目数等于第一步的最高频率的列表。此列表中每个槽的索引将包含频率计数等于索引的单词列表。例如，在文档中出现 3 次的单词会出现在 list[3] 中。遍历哈希映射并将单词插入列表中的适当位置。这一步是 O(n) 复杂度。
第三步：反向遍历列表，输出所有单词。这一步是 O(n) 复杂度。
总体而言，该算法将在O(n) 时间内完成您的任务，而不是快速排序所需的 O(nlogn)。
于 2009-06-05T04:14:25.883 回答
1
在我测试过的几乎所有案例中，Quicksort 对我来说都是最好的。但是，我确实有两个案例表明 Combsort 是最好的。在这些情况下，combsort 可能会更好，因为代码太小，或者由于数据的排序方式有些怪异。
任何时候排序出现在我的个人资料中，我都会尝试主要的排序。我从来没有任何东西能同时超过 Quicksort 和 Combsort。
于 2009-06-05T18:38:37.517 回答
0
我认为您想要按照以下帖子中的说明执行操作：
http://karephul.blogspot.com/2008/12/groovy-closures.html
支持闭包的语言使解决方案变得更加容易，例如 Eric 提到的 LINQ。
于 2009-06-05T18:31:30.633 回答
0
对于大型集合，您可以在信息检索中使用所谓的“基于排序的索引”，但对于 50,000 个单词，您可以使用以下内容：
- 将整个文件读入缓冲区。
- 解析缓冲区并使用 struct token { char *term, int termlen; 构建一个令牌向量 } term 是指向缓冲区中单词的指针。
- 按术语对表进行排序（字典顺序）。
- 设置entrynum = 0，遍历term向量，当term为new时，将其存储在向量中：struct { char *term; 整数频率；} 在索引 entrynum 处，将频率设置为 1 并增加条目号，否则增加频率。
- 按频率降序对向量进行排序。
于 2009-06-13T09:02:50.937 回答
0
您还可以尝试实施也称为 Trie 的数字树。这是链接
于 2013-01-28T04:41:51.350 回答