c - C：排序方法分析

Question

我有很多不同的排序算法，它们都有以下签名：

void <METHOD>_sort_ints(int * array, const unsigned int ARRAY_LENGTH);

是否有任何用于排序的测试套件可用于进行经验比较？

Answer 1

这个详细的讨论，以及链接到您可能会发现有用的大量相关网页，还描述了一组用于测试排序算法的有用输入数据（请参阅链接页面了解原因）。总结：

1. 完全随机改组的数组
2. 已经排序的数组
3. 已经按逆序排列的数组
4. 电锯阵列
5. 相同元素的数组
6. 具有 N 个排列的已排序数组（N 为大小的 0.1% 到 10%）
7. 已按 N 个排列倒序排列的数组
8. 具有重复（或关闭）键的正态分布数据（仅用于稳定排序）
9. 伪随机数据（标普 500 或其他十年指数的每日值可能是一个很好的测试集；它们可从 Yahoo.com 获得）

Answer 2

排序的权威研究是Bob Sedgewick的博士论文。但是在他的算法教科书中有很多很好的信息，这些是我寻找测试套件和方法的前两个地方。如果你最近上过一门课程，你会比我知道的更多；上次我有一个课程，最好的方法是使用快速排序到大小为 12 的分区，然后对整个数组运行插入排序。但答案的变化与硬件一样快。

Jon Bentley 的 Programming Perls 书籍有一些关于排序的其他信息。

您可以快速创建一个测试套件，其中包含

• 随机整数

• 排序整数

• 反向排序的整数

• 有序整数，轻微扰动

如果有记忆，这些是排序算法最重要的情况。

如果您要对不适合缓存的数组进行排序，则需要测量缓存效果。 valgrind慢的话是有效的。

Answer 3

该站点显示了使用四个组的各种排序算法：http: //www.sorting-algorithms.com/

除了诺曼答案中的四组之外，您还想检查排序算法，其中包含在数字中有一些相似之处的数字集合：

• 所有整数都是唯一的
• 整个集合中的相同整数
• 很少有唯一键

更改集合中元素的数量也是一个很好的做法，用 1K、1M、1G 等检查每个算法，看看该算法对内存的影响是什么。

Answer 4

sortperf.py 有一套精心挑选的基准测试用例，用于支持在此处找到的文章，并使 timsort 在 Python 中成为多年前的排序方式。请注意，由于 Josh Block（参见此处)，所以我想他们已经编写了自己的基准测试用例版本——但是，我无法轻易找到对它的引用。（timsort，一种稳定的、自适应的、迭代的自然归并排序变体，特别适用于具有引用对象语义的语言，如 Python 和 Java，其中“数据移动”相对便宜 [[因为所有被移动的都是引用，也就是指针，而不是无限大小的 blob；-)]]，但是比较可能相对昂贵 [[因为比较函数的复杂性没有上限——但这适用于任何可以通过自定义自定义排序的语言比较或密钥提取功能]]）。