4

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

4

9 回答 9

17

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

回到 COBOL、FORTRAN 等时代……为电话公司工作的开发人员必须获取包含活动电话号码的相对大量数据（我相信它在纽约市地区），然后进行排序那个清单。最初的实现使用堆排序（这些是 7 位电话号码，并且在排序过程中发生了大量磁盘交换，因此堆排序是有意义的）。

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

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

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

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

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

于 2008-10-27T03:31:20.540 回答
9

一般没有。

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

于 2008-10-27T03:16:43.267 回答
3

实现自己的排序算法类似于优化，正如查尔斯·安东尼·理查德·霍尔爵士所说，“我们应该忘记小的效率，比如大约 97% 的时间：过早的优化是万恶之源”。

于 2008-10-27T03:32:37.477 回答
2

某些库（例如 Java 自己的 Collections.sort）根据可能适用于您的标准实现排序，也可能不适用于您。例如，Collections.sort 使用归并排序是因为它的 O(n log(n)) 效率以及它是就地排序的事实。如果两个不同的元素具有相同的值，则原始集合中的第一个元素保持在前面（有利于根据不同条件进行多遍排序（首先扫描日期，然后查找名称，集合保持名称（然后日期）排序））但是，如果您想要更好的常量或有一个特殊的数据集，那么实现您自己的快速排序或基数排序可能更有意义，具体到您想要做什么。

也就是说，所有操作在足够小的 n 上都很快

于 2008-10-27T03:51:14.010 回答
1

简短的回答；不，除了学术兴趣。

于 2008-10-27T03:19:06.913 回答
1
  • 您可能希望对排序实现进行多线程处理。
  • 您可能需要比 Quicksorts O(n log n) 更好的性能特征，例如 bucketsort。
  • 您可能需要稳定的排序，而默认算法使用快速排序。特别是对于用户界面，您会希望排序顺序保持一致。
  • 更有效的算法可能适用于您正在使用的数据结构。
  • 由于堆栈溢出（例如，您正在对大量数据进行排序），您可能需要默认排序算法的迭代实现。

无穷无尽。

于 2008-10-27T04:57:48.227 回答
0

几个月前，Coding Horror 博客报道了某个平台的排序算法非常糟糕。如果您必须使用该平台，那么您肯定想要实现自己的平台。

于 2008-10-27T03:32:12.160 回答
0

通用排序的问题已经被研究到了地狱，所以担心学术兴趣之外的问题是没有意义的。但是，大多数排序不是在通用输入上完成的，通常您可以使用数据的属性来提高排序速度。

一个常见的例子是计数排序。事实证明，对于通用比较排序，O(n lg n) 是我们希望做到的最好的。

但是，假设我们知道要排序的值在固定范围内的范围，比如 [a,b]。如果我们创建一个大小为 b - a + 1 的数组（默认一切为零），我们可以线性扫描数组，使用这个数组来存储每个元素的计数 - 产生线性时间排序（在数据的范围内） ) - 打破 n lg n 界限，但这仅仅是因为我们正在利用数据的特殊属性。有关更多详细信息，请参见此处。

所以是的，编写自己的排序算法很有用。注意你正在分类的东西，你有时会想出显着的改进。

于 2008-10-27T03:45:06.220 回答
0

如果您有实现排序算法的经验并了解数据特征对其性能的影响方式，那么您已经知道问题的答案。换句话说，您已经知道像快速排序这样的东西在几乎排序的列表中具有行人性能。:-) 而且，如果您的数据具有某些结构，则某些排序（几乎）是免费的。等等。

否则，没有。

于 2008-10-27T06:01:14.417 回答