有没有理由实现我自己的排序算法？

排序已经研究了几十年,所以现在任何编程平台(java,.NET等)提供的排序算法肯定都不错,对吧？有没有理由覆盖像System.Collections.SortedList这样的东西？

1> Kevin Day..：

---

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

回到COBOL,FORTRAN等的时代......一家为电话公司工作的开发人员不得不接收一大堆由活跃电话号码组成的数据(我相信它是在纽约市区),并排序那份清单.原始实现使用堆排序(这些是7位数的电话号码,并且在排序期间进行了大量的磁盘交换,因此堆排序很有意义).

最终,开发人员偶然发现了一种不同的方法:通过实现一个,并且每个电话号码中只有一个存在于他的数据集中,他意识到他不必将实际的电话号码存储在内存中.相反,他将整个7位数的电话号码空间视为一个非常长的阵列(每个字节8个电话号码,1000万个电话号码只需要超过1兆的电流来捕获整个空间).然后,他通过他的源数据进行了一次传递,并将他找到的每个电话号码的位设置为1.然后,他最后通过位数组寻找高位并输出已排序的电话号码列表.

这种新算法比堆排序算法快得多(速度至少快1000倍),并消耗了大约相同的内存量.

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

如果你的应用程序都是关于排序的,并且你真的知道你的问题空间,那么你很有可能想出一个特定于应用程序的算法,它可以胜过任何通用算法.

但是,如果排序是您的应用程序的辅助部分,或者您只是实现了一个通用算法,那么一些非常聪明的大学类型已经提供了一种比您能够获得的更好的算法的机会非常非常好.起来.如果你可以在内存中保存内容,快速排序真的很难被击败,并且堆排序对于大规模数据集排序非常有效(尽管我个人更喜欢使用B + C类型的实现用于堆b/c它们被调整到磁盘分页性能).

2> BoltBait..：

---

一般没有.

但是,您比编写这些排序算法的人更了解您的数据.也许您可以为您的特定数据集提出一种比通用算法更好的算法.

---

还值得一提的是，您必须问自己：“即使我的算法更快，它是否可以感知？是否值得冒险尝试提高程序的正确性或增加这种增量提速的成本/开发时间？”

---

在这些情况下，只要语言支持，您可能会受益，只需提供一个自定义比较器，而不是完全重新实现标准的排序算法即可。