我有一个至少包含 2000 个随机唯一整数的数组，每个整数的范围为 0 < n < 65000。
我必须对其进行排序，然后获取数组中随机值的索引。这些操作中的每一个都必须尽可能快。对于搜索，二进制搜索似乎效果很好。
对于排序，我使用了标准快速排序算法 (qsort)，但有人告诉我，根据给定的信息，标准排序算法将不是最有效的。所以问题很简单 - 使用给定信息对数组进行排序的最有效方法是什么？对此完全不解。
最佳答案
我不知道为什么告诉你这件事的人会如此神秘，但实际上 qsort 并不是在 C++ 中对整数(或一般任何东西)进行排序的最有效方法。请改用 std::sort。
可能您可以针对规定的特殊情况(0-65k 范围内的 2000 个不同的随机整数)改进实现的 std::sort，但是您不太可能做得更好，而且几乎肯定不值得付出努力。我能想到的事情可能会有所帮助:
使用快速排序，但使用不同的主元选择或不同的阈值以从您的
排序实现使用的切换到插入排序。这基本上是在修补。使用某种并行排序。 2000 个元素太小了，我怀疑创建额外线程的时间会立即扼杀任何性能改进的希望。但是，如果您要进行很多排序，那么您可以平均创建所有线程的成本，并且只需担心线程同步的开销，而不是线程创建的开销。
就是说，如果您生成数组并对其进行排序，然后只查找其中的一个 值，然后生成一个新数组，那么每次都对整个数组进行排序会浪费精力。您可以只运行整个数组，计算小于目标值的值的数量:这个计数就是它应该拥有的索引。使用 std::count_if 或短循环。
Each of these operations have to be as fast as possible.
这不是合法的软件工程标准。通过足够多的几个月或几年的工程努力，几乎任何事情都可以稍微快一点——没有什么复杂的东西是“尽可能快”的，即使是这样你也无法证明它不能更快，而且即使您可以在某个地方或即将发明新硬件，最快的解决方案也不同且更好。除非你打算把你的一生都花在这个任务上并最终失败，否则获得一个更现实的目标;-)
关于c++ - 随机唯一整数的非标准排序算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21388732/