在哪里可以找到几个重要的排序算法测试用例？

Question

我想根据我的一些想法开发一种非常有效的排序算法。问题是我想根据现有的大多数备受赞赏的排序算法来测试我的算法的效率。

理想情况下，我希望找到：

• 大量的排序测试，对于为我提供算法的效率而言非常重要
• 大量已经存在且高度优化的排序算法（及其代码 - 无论语言）
• 甚至更好，为排序算法开发人员提供足够环境的软件

这是我之前发现的一篇文章，其中包含 2 个表，其中比较了 timsort、quicksort、dual-pivot fastsort 和 java 6 sort：http://blog.quibb.org/2009/10/sorting-algorithm-shootout/ 我可以在这些表中看到这些 TXT 文件（从 1245.repeat.1000.txt 到equential.10000000.txt）包含这些算法的测试用例，但我在任何地方都找不到原始 TXT！

任何人都可以向我指出许多排序测试用例和/或许多高效排序算法的链接吗？ （这是我最感兴趣的测试用例，排序算法遍布互联网）

提前非常感谢！

Answer 1

有几点：

• 快速排序对正向和反向排序列表很疯狂，因此它需要其他列表类型。
• 对随机数据进行测试很好，但如果您想比较不同算法的性能，这意味着您无法每次都生成新的随机数据，否则您的结果将不可靠。我认为您应该尝试提出一种伪“随机”算法，该算法按照基于条目数的顺序写入数据。这样，为大小为 n、10n 和 100n 的列表生成的数据将相似。
• 排序测试主要不是关于速度（直到算法最终确定），而是与条目的比较比率。如果一种排序需要列表中每个条目 15 次比较，而同一列表需要另外 12 次比较，则第二种排序会更高效，即使它的执行时间是两倍。对于更琐碎的排序概念，必要的交换次数也将发挥作用。
• 为了进行测试，使用 RAM 中的整数向量。如果该算法运行良好，则可以将整数向量转换为索引向量，并将其放入包含要比较的数据的缓冲区中。这样的算法将根据它们指向的数据对因数向量进行排序。