我不时浏览网络，寻找有趣的算法和数据结构，以放入我的绝招中。一年前，我遇到了Soft Heap数据结构，并了解了近距离排序的知识。

其背后的想法是，如果我们可以忍受排序算法有点作弊的事实，则有可能打破基于比较的排序的O(n log n)障碍。我们会得到一个几乎排序的列表，但是我们还必须忍受一些错误。

我在测试环境中试用了这些算法，但从未发现它们的用途。

那么问题来了：在实践中，有没有人使用过近排序？如果是这样，在哪种应用程序中？我们能考虑一个正确的案例吗？

解决方案

这是一个完全的猜测，但是考虑到对搜索结果进行排序时"相关性"度量标准的固有主观性，我敢冒险地说，是否对它们进行完美排序并不重要。对于建议也可以这样说。如果我们能以某种方式安排算法的所有其他部分为O(n)，那么我们可能会避免排序。

还应注意，在最坏的情况下，"几乎排序"的数据不符合"几乎排序"的一种可能的直观想法，即它只有很少的反转。这样做的原因是，如果数据仅具有O(n)个反演，则可以使用插入排序或者混合排序(即双向气泡排序)在O(n)时间内完成对数据的排序。因此，我们不可能在O(n)的时间内完全未排序就达到了这一点(使用比较)。因此，我们正在寻找的应用程序是对大多数数据子集进行排序而其余数据则分散的应用程序，而不是针对要求每个元素都接近其正确位置的应用程序。

只是在这里推测，但是我想的一件事是数据库查询优化。

以声明性语言(例如SQL)进行的数据库查询必须转换为称为"执行计划"的分步程序。一个SQL查询通常可以转换为许多这样的执行计划，这些计划都给出相同的结果，但是性能却有很大不同。查询优化器必须找到最快的一个，或者至少找到相当快的一个。

基于成本的查询优化器具有"成本函数"，可用于估计给定计划的执行时间。详尽的优化器会仔细研究所有可能的计划(以"一切皆有可能"的某个值)并选择最快的计划。对于复杂的查询，可能的计划数量可能会过高，导致优化时间过长(甚至在我们开始在数据库中搜索之前！)，因此还存在一些非详尽的优化器。他们只看一些计划，也许在选择哪个计划时会随机考虑。之所以可行，是因为通常会有大量的"好的"计划，而找到绝对最佳的计划可能并不那么重要-选择5秒钟的计划而不是2秒钟的最佳计划可能更好，如果需要几分钟的优化才能找到2秒钟的计划。

一些优化算法使用"有前途的"(部分)计划的排序队列。如果找到绝对最佳的计划并不重要，也许可以使用几乎排序的队列？

另一个想法(我仍然在推测)是分时系统中进程或者线程的调度程序，在该调度程序中，如果某个进程或者线程比严格按优先级严格排序的时间晚了几毫秒，那么它可能并不重要。 。

任何地方

• 你应该做出快速反应，
• 我们不会向客户承诺确切的行为，
• 但在内部我们有一些规则

我们可以使用它。基于规则的"不太严格"优先级队列怎么样？在哪里有用？也许是线程/进程/资源调度。在线程/进程调度中，我们实际上并不能保证任何一个线程都会先行，后行或者后行，但是通常我们希望给每个人一些机会。我们可能需要强制执行宽松规则，这样它才是抢先的，优先的。

资源进度表示例将响应比萨的交付或者将书本运送给人们等。我们不能在期望确定性结果的地方使用它，但是在现实生活中，有很多示例无法确定性/可预测性。

在很多"贪婪"启发式方法中，我们会定期选择一组中的最小值。贪婪的启发式方法并不完美，因此即使我们选择了最小的方法，也无法保证最终的答案是最佳的。实际上，对于GRASP meta-heuristic，我们有意引入随机误差，以便获得多个最终解决方案并选择最佳解决方案。在那种情况下，在排序例程中引入一些错误以换取速度将是一个很好的权衡。

接近分类的一个常见应用是当人们进行成对比较时，我们不想问他们那么多的问题。

假设我们有很多物品需要人类通过成对比较进行排序。如果我们愿意接受排序不准确的情况，则可以大大减少需要进行的比较次数。例如，我们可能不在乎相邻项目是否已交换，只要首选项目在顶部即可。