algorithm - 高效排序算法的实际重要性

Question

我一直在四处寻找，试图了解任何需要排序且其效率很重要的实际应用，但找不到任何东西。

我能找到或想到的唯一示例要么不需要总排序(例如在查找 100 个最佳结果或中位数时)，要么排序效率几乎不重要(例如每年对包含学生姓名或过去的交易)。

• 在对网络搜索结果进行排序时，只需找到几十个排名靠前的结果并进行排序，而不是整个互联网，因此不需要或不实用经典排序算法。

• 在对电子表格进行排序时，它是按三轴拉斯维加斯随机快速排序还是按插入排序排序都无关紧要。

• 使用排序数组作为集合或关联数组似乎实际上不如使用哈希表有效。

所以我的问题是:需要整体排序并且其效率是瓶颈的实际(“现实生活”)示例有哪些？我对comparison sorting的申请特别好奇.

---

更新。

我在 lecture notes 中偶然发现了这个短语史蒂文斯基纳:

Computers spend more time sorting than anything else, historically 25% on mainframes.

有了一些细节，这可以完美地回答我的问题。我在哪里可以找到此统计数据的来源，最好是有关大型机完成的排序的种类和应用的一些详细信息？

Answer 1

在一些图形渲染算法中，需要按照从后到前的顺序绘制对象。一个很好的例子是透明粒子:可以有数十万个，并且由于透明性，传统的深度缓冲不起作用。因此，您需要按照与相机的距离对这些粒子进行排序，并以每秒 60 帧的速度对它们进行排序。

有趣的是，如果粒子的顺序变化不大(粒子运动相对较慢，相机运动很少)，那么粒子阵列在下一帧中已经“大部分排序”，并且简单的冒泡排序或插入排序实际上可以正常工作。但是在创建了许多粒子或相机快速移动的帧上，排序性能可能变得很重要，因为每一帧都有很多其他事情要做。