sorting - 有什么理由来实现我自己的排序算法吗？

Question

排序已经研究了几十年，所以现在任何编程平台(java、.NET 等)提供的排序算法肯定都很好，对吧？是否有任何理由覆盖 System.Collections.SortedList 之类的内容？

Answer 1

在某些时候，您对数据的深入理解可以产生比任何可用的通用算法更有效的排序算法。我在 SO 的另一篇文章中分享了这种情况的一个例子，但我会分享它只是为了提供一个实例:

回到 COBOL、FORTRAN 等时代......为电话公司工作的开发人员必须获取由事件电话号码组成的相对大量数据(我相信它在纽约市地区)，并进行排序那个 list 。最初的实现使用了堆排序(这些是 7 位电话号码，并且在排序过程中发生了大量磁盘交换，因此堆排序是有意义的)。

最终，开发人员偶然发现了一种不同的方法:通过意识到他的数据集中每个电话号码只能存在一个，他意识到他不必将实际的电话号码本身存储在内存中。相反，他将整个 7 位电话号码空间视为一个非常长的位数组(每字节 8 个电话号码，1000 万个电话号码只需要超过 1 兆字节就可以捕获整个空间)。然后他对他的源数据进行了一次遍历，并将他找到的每个电话号码的位设置为 1。然后他对位数组进行了最后一次遍历，寻找高位并输出电话号码的排序列表。

这种新算法比堆排序算法快得多(至少快 1000 倍)，并且消耗的内存量大致相同。

我会说，在这种情况下，开发人员开发自己的排序算法绝对有意义。

如果您的应用程序完全是关于排序的，并且您真的了解您的问题空间，那么您很可能想出一种击败任何通用算法的特定于应用程序的算法。

但是，如果排序是您的应用程序的辅助部分，或者您只是在实现通用算法，那么很有可能一些非常聪明的大学类型已经提供了一种比您所能提供的任何算法都更好的算法起来。如果你能在内存中保存东西，快速排序真的很难被击败，堆排序对于海量数据集排序非常有效(尽管我个人更喜欢对堆 b/c 使用 B+Tree 类型的实现，它们被调整到磁盘分页表现)。