近排序算法 - 何时使用？

Question

我不时浏览网页,寻找有趣的算法和数据结构,放入我的技巧包中.一年前,我遇到了Soft Heap数据结构并了解了近乎排序.

这背后的想法是,如果您可以接受排序算法作弊的事实,则可以打破基于比较的排序的O(n log n)障碍.你得到一个几乎排序的列表,但你也必须忍受一些错误.

我在测试环境中使用了算法,但从未找到它们的用途.

所以问题是:有没有人在实践中使用过近排序？如果是这样的应用程序？你能想到一个近距离排序是正确的用例吗？

Answer 1

这是一个完全的飞行猜测,但鉴于在对搜索结果进行排序时"相关性"度量的固有主观性,我冒昧地认为它们是否完美排序并不重要.对于建议也可以这样说.如果你能以某种方式安排算法的每个其他部分都是O(n)那么你可能会想要避免排序.

还要注意,在最坏的情况下,您的"近乎排序"的数据不符合"几乎排序"的一个可能的直观概念,即它只有少量的反转.这样做的原因只是如果您的数据只有O(n)反转,那么您可以使用插入排序或鸡尾酒排序(即双向冒泡排序)在O(n)时间内完成排序.因此,在O(n)时间内(使用比较),你不可能从完全未排序到达这一点.因此,您正在寻找对数据的大部分子集进行排序而其余部分是分散的应用程序,而不是针对要求每个元素都接近其正确位置的应用程序.

Answer 2

有很多“贪婪”启发式方法，您可以定期选择集合中的最小值。贪婪启发式算法并不完美，因此即使您选择了最小值，也不能保证得到最好的最终答案。事实上，GRASP元启发式，你故意引入随机错误，以便你得到多个最终解决方案并选择最好的一个。在这种情况下，在排序例程中引入一些错误以换取速度将是一个很好的权衡。