Java和.NET：为什么默认使用不同的排序算法？

Question

我想知道为什么Java和.NET Framework默认使用不同的排序算法。

在Java中，Array.Sort()默认使用归并排序算法，正如Wikipedia.com所述：

在Java中，Arrays.sort()方法根据数据类型使用归并排序或经过调整的快速排序，并在实现效率时在要排序的元素少于七个的情况下切换到插入排序。

在.NET Framework中，Array.Sort/List.Sort()使用快速排序作为默认排序算法（MSDN）：

List.Sort()使用Array.Sort，它使用快速排序算法。这种实现执行不稳定排序；也就是说，如果两个元素相等，则它们的顺序可能无法保留。相比之下，稳定排序保留相等元素的顺序。

通过查看"算法比较"表格，我们可以看到两种算法在最坏情况和内存使用方面有着非常不同的行为：

Java和.NET都是用于企业解决方案开发的优秀框架，两者都有嵌入式开发的平台。那么为什么它们默认使用不同的排序算法呢？有什么想法吗？

编辑： 我看到已经有两个人投票将此问题关闭为“没有建设性”。我认为Java和.NET是最流行的开发框架，因此找到任何关于这样的决定的非平凡和有趣的想法，甚至是事实，都会非常有趣。

- sll

---

因为Java和.NET是由两个完全不同的公司开发的两种完全不同的技术。 - BoltClock

+1，有趣的问题。但我认为它可能更适合在Programmers.SE上，因为这更像是一个“白板问题”。 - Daniel Pryden

Java中的内存是2n，因为数组被复制，而列表首先被转换为数组。 - bestsss

回答：Java 设计师（或 java.util. 团队）决定使用归并排序，因为它不会重新排列具有相同顺序/优先级的元素，也可以防止 DoS 攻击。我记得读过这两个方面的内容。至于 .Net，我猜是为了遵循 C 排序。 - bestsss

除了我以外，有没有其他人收到Java7不再使用MergeSort的备忘录？对于基本数据类型，他们采用DualPivotQuicksort算法；对于对象，他们采用TimSort算法（Python用户应该本能地熟悉这个算法）。实际上，我相当确定在<=6中，Java也使用QuickSort算法进行某些排序 - 但我可能记错了。而且，它仍然会对小数组使用一些插入排序等算法。 - Voo

继续讨论Programmers.SE - http://programmers.stackexchange.com/questions/108624/java-and-net-why-different-sorting-algorithms-are-used-by-default - sll

Answer 1

两家不同公司的开发团队对于其框架和组件通常的使用情况得出了不同的结论，并决定据此进行实施。

- Oded

---

是的，我能想象这种情况。但我相信企业解决方案有一套常见问题，排序算法将会有所帮助，而归并排序和快速排序都有很大不同。 - sll

@sll - Sun和Microsoft是不同的公司，拥有不同的客户群。为什么他们要在各自的框架上合作呢？ - Oded

不，我不是指合作，我是指Java和.NET都用于解决常见的企业问题，比如“问题”，我认为在深入独立分析后，这两个框架会发现同样的算法作为默认算法非常有用。如果我的想法表达不够清晰，对不起，我不是以英语为母语的人，但我正在学习 :) - sll

@sll - 很有可能每家公司从他们的分析中得出了不同的结论。 - Oded

这个观点对我来说很合理，但不幸的是我们不能看到其他的意见，看起来这个问题真的不适合在SO上讨论... 我希望有人能投票重新开启问题或者帮忙重新表述一下使其被接受为建设性的，谁知道呢... 无论如何，感谢Oded！ - sll