<分区>
在通常情况下，对包含约 1000 个简单项(如整数或 float )的数组进行排序已经足够快，因此实现之间的微小差异并不重要。
但是，如果您需要对由某些类似过程生成的 N 个中等大小的数组进行排序，或者只是具有某种相关性，该怎么办？
我故意让神秘的数组生成器的细节和生成的数组之间的关系含糊不清。任何适用的算法都可以指定一个尽可能大的域，它们将在最有用的时候工作。
编辑:让我们通过让数组成为独立样本来缩小范围。将要生成的数组存在一个不变的概率分布。隐含地，数组中的元素有一个稳定的概率分布，但它是有条件的——数组中的元素可能不是独立的。似乎很难利用数组中元素之间的关系，但我可能是错的。如果需要，我们可以通过让数组中的元素独立来进一步缩小范围。在那种情况下，问题是如何有效地学习和使用数组中元素的概率分布。
最佳答案
这是一篇关于 self improving sorting algorithm 的论文.我非常擅长算法和机器学习，但这篇论文对我来说绝对不是一本容易读的书。
摘要是这样说的
We investigate ways in which an algorithm can improve its expected performance by fine-tuning itself automatically with respect to an arbitrary, unknown input distribution. We give such self-improving algorithms for sorting and clustering. The highlights of this work: a sorting algorithm with optimal expected limiting running time ... In all cases, the algorithm begins with a learning phase during which it adjusts itself to the input distribution (typically in a logarithmic number of rounds), followed by a stationary regime in which the algorithm settles to its optimized incarnation.
关于对具有潜在相似特征的许多数组进行排序的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22490030/