有效排序算法的实用重要性

Question

我一直在四处寻找，试图了解任何需要排序的实际应用程序，以及排序的效率，但什么也找不到。

我能找到或考虑的唯一例子要么不需要完全排序(比如在寻找100个顶级结果或中值时)，要么排序效率并不重要(比如，每年对学生姓名或过去的事务进行一次排序)。

• 在对网络搜索结果进行排序时，只需要找到几十个排名最高的结果，而不是所有的互联网，所以经典的排序算法是不需要的，也不实用。
• 在对电子表格进行排序时，它是按照三轴式拉斯维加斯随机快速排序还是按插入排序几乎没有关系。
• 使用排序数组作为集合或关联数组似乎比使用哈希表的效率要低。

因此，我的问题是:在需要总排序的情况下，和(其效率是瓶颈)的实用示例(“现实生活”)是什么？我对https://en.wikipedia.org/wiki/Comparison_sort的应用程序特别感兴趣。

更新。

我偶然发现了史蒂文·斯基纳(Skiena)在课堂讲稿中的这个短语：

计算机花在排序上的时间比其他任何事情都要多，历史上有25%的时间花在大型机上。

有了一些细节，我的问题就能得到一个完美的答案。我在哪里可以找到这些统计数据的来源，最好是提供一些关于大型机进行排序的种类和应用的细节？

Answer 1

想象一下，你有一份银行账户交易(存款和提款)的每日列表。每天有数以百万计的账户和数百万笔交易。每天晚上，您必须更新帐户以反映这些交易，并计算当天应计利息，并打印一份按帐户订购的报表，该报表显示每个帐户及其日常活动。

其中一种方法是按顺序遍历列表，读取事务并更新数据库中的帐户。这是可行的，但也有几个缺点，包括：

1. 如果单个帐户有许多事务，则为每个事务支付检索和更新帐户的代价。考虑到一个商业账户每天可能有数千笔交易，这些成本加起来就会增加。
2. 典型的规则是在提款前记录存款，以防止透支。如果一个账户的余额为0，并且交易列表在10美元的存款之前提取了5美元，系统会记录透支，而不是这样。
3. 在记录所有交易之后，打印报告将需要对数据库进行单独扫描。

解决这些问题的方法是按帐户和类型对交易列表进行排序(首先是存款)。然后，更新是一个简单的合并操作。您按帐号顺序读取数据库和事务列表，为该帐户应用任何事务，计算利息，打印输出行，并将更新的记录写入数据库。

其结果比对每个事务执行读-更新-写入要快得多，并且它消除了我前面概述的#2和#3的问题。排序和合并决定了整晚的更新和几个小时的更新之间的区别。

另外，用于处理大数据的MapReduce (和Hadoop)也很好地利用了排序。如果没有高性能的排序算法，这些编程模型就是不可能实现的。

当您需要将多个大型数据流合并到单个输出流(这些应用程序数量众多)时，排序和合并方法是很有用的。有时其他技术可能会更快，但是碳烟合并是可靠和持久的，正如MapReduce所示，扩展性很好。

Answer 2

在一些图形绘制算法中，对象需要按背靠背顺序绘制。一个很好的例子是透明粒子:可能有成千上万的粒子，而且由于透明，传统的深度缓冲无法工作。所以你需要根据距离对这些粒子进行分类，并保持它们的排序，以每秒60帧的速度。

有趣的是，如果粒子的顺序变化不大(粒子运动相对较慢，相机移动较小)，那么粒子阵列将在下一帧中“大部分排序”，而简单的气泡排序或插入排序实际上可以工作得很好。但是在产生许多粒子的帧上，或者相机快速移动时，排序性能就变得非常重要，因为每个帧都有很多其他的事情要做。