3

我想根据我的一些想法开发一种非常有效的排序算法。问题是我想针对已经存在的大多数高度赞赏的排序算法来测试我的算法的效率。

理想情况下，我想找到：

  • 一大堆排序测试对于为我提供算法的效率非常重要
  • 大量已经存在且经过高度优化的排序算法（带有它们的代码 - 无论是哪种语言）
  • 更好的是，为排序算法开发人员提供足够环境的软件

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

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

非常感谢您！

4

1 回答 1

1

一些东西：

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