C语言：排序方法分析

Question

我有很多不同的排序算法，它们都具有以下特征：

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

有没有任何针对排序的测试套件，可以用于进行实证比较？

- Ande Turner

---

将值类型参数作为const传递没有意义。我猜它也没有什么坏处，但是这是毫无意义和啰嗦的。 - unwind

如果排序算法是适当实现的标准算法，那么已经有复杂度分析数据可用（谷歌搜索即可），那么进行排序分析的目的是什么？ - Learner

@unwind: 我更喜欢将常量值声明为常量值。 @learner: a) 许多不是标准的。b) 我有一些算法，由于内存和缓存的原因在不同的机器上表现不同，不幸的是在这些情况下泛化是不可接受的。 - Ande Turner

听起来像是我几年前数据结构课上要做的一个项目 :) 之后，就是插入、删除和迭代各种容器结构并进行比较。 - crashmstr

Answer 1

这篇详细的讨论文章不仅链接了大量相关网页，对于测试排序算法也提出了一组有用的输入数据（原因请参见链接页面）。总结如下：

1. 完全随机重排的数组
2. 已排序的数组
3. 按相反顺序排序的数组
4. 电锯式数组
5. 由相同元素构成的数组
6. 有N个排列的已排序数组（其中N为大小的0.1%至10%）
7. 有N个排列的按相反顺序排序的已排序数组
8. 具有重复（或接近）关键字的正态分布数据（仅适用于稳定排序）
9. 伪随机数据（例如十年间S&P500或其他指数的日常价值可能是一个很好的测试集，请从Yahoo.com获取）。

- ire_and_curses

Answer 2

排序的权威研究是Bob Sedgewick的博士论文。但他的算法教材中也有许多有用的信息，这是我查找测试套件和方法的前两个地方。如果您最近上过课程，您会比我更了解；上次我上课时，最好的方法是使用快速排序将分区大小降至12，然后在整个数组上运行插入排序。但随着硬件的更新，答案也在迅速变化。

Jon Bentley的编程珠玑书籍中还有一些关于排序的信息。

您可以快速创建包含以下内容的测试套件：

- 随机整数 - 排序整数 - 反向排序的整数 - 排序整数，稍微扰动一下

如果我没记错，这些是排序算法最重要的情况。

如果您想要对无法适应缓存的数组进行排序，则需要测量缓存效果。valgrind 是一个有效但缓慢的工具。

- Norman Ramsey

Answer 3

这个网站展示了各种排序算法，分为四组： http://www.sorting-algorithms.com/ 除了 Norman 回答中提到的四组外，您还可以通过一些相似数字的集合来检查排序算法：

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

同时，改变集合中元素的数量也是一个好的实践，可以使用 1K、1M、1G 等不同规模的数据来检查每个算法，以了解该算法的内存使用情况。

- Dror Helper

Answer 4

sortperf.py是一个精选的基准测试用例套件，被用来支持在多年前发现的文章（这里）并使timsort成为Python中的排序算法。请注意，最终Java可能也会采用timsort，这要归功于Josh Block（请参见此处），因此我想他们已经编写了自己版本的基准测试用例，但是我很难找到相关参考资料。（timsort是一种稳定、适应性强、迭代的自然合并排序变体，特别适用于具有引用-对象语义的语言，如Python和Java，在这些语言中，“数据移动”相对较便宜[[因为移动的只是引用或指针，而不是大小不受限制的二进制大块；-)]，但比较代价相对较高[[因为没有上限的比较函数复杂度——但这同样适用于任何通过自定义比较或键提取函数来自定义排序的语言]]。）

- Alex Martelli