1回答

liuyubobobo

2022-04-24

首先纠正一点：Java 标准库的实现中，并非只有归并排序。

在 Java 标准库中，对基本数据类型数组的排序，比如你想对 int[] 做排序，使用的是类似于三路快排的排序方式（课程后续会介绍）；

对类对象的排序，比如你想对 ArrayList<Person> 做排序，会使用类似归并排序的方式（其实是有一定有花的自底向上的归并排序，但基本原理差不多。）

有这个区别的核心原因在于：排序算法的稳定性。归并排序是稳定的，而快排是不稳定的。（对于这个概念，课程后续也会介绍。）

==========

对于基本数据类型，由于保证了数据的“域”肯定只有一个，所以不会有排序稳定性的需求，使用快排是没有问题的。

而对于类对象的排序，因为一个类对象中可能包含多个域，所以潜在的（只是潜在的，不是一定的），排序算法的调用者可能需要排序的稳定性，所以默认直接使用一种稳定排序算法（归并排序极其变种是稳定排序的最好选择。）

另外一个考量是：自底向上的归并排序不需要利用排序容器的“随机性”，所以，归并排序可以很好地作用于诸如链表这样的结构，而快排的思想不能用于链表这种结构（印象里对于这一点，课程中有提及。）

再有一个区别是，快排通常都使用递归实现，而自底向上的归并排序不需要递归。这在大多数软件开发种不成问题，但是在一些特殊的情形下，可能会构成问题（比如由于硬件环境的底层限制导致递归的栈空间很小，甚至不允许递归，尤其是在嵌入式开发中。）而 Java 作为一种跨平台的语言，是需要对于这种极端情况给出解决方案的。

（但其实，如果真的在这种极端情况下，希尔排序或许是更好的选择。）

==========

最后，其实，对于两种排序的性能差异，在如今的软件开发中，尤其是上层业务开发中，并不那么敏感（真要那么的性能敏感，或许从根子上不应该使用 Java）。其实在当今软件开发中，很多时候第一考虑的要素并非性能，而是通用性，易用性，等这方面的东西。所以，如果仅仅从性能方面考量，会有很多解释不通的东西。

比如排序算法是存在 O(n) 的算法的，并且在一些场景下显著优于快排或者归并排序（课程后续讲到这些排序的时候会给出比较的测试用例），那大多数语言的标准库为什么不提供这些算法？因为这些情况太特殊了，在 99.99% 的情况下，快排和归并是最好的选择（一个不稳定，一个稳定）。这里的考量，就是通用性。

再比如大多数语言标准库中的字符串匹配算法就是去逐一字符匹配，而不是什么高大上的 kmp。为什么？因为在正常文本下，简单地逐一匹配就足够快。在正常文本下，kmp 反而会慢。只有在极其极其特殊的情况下，逐一做匹配才会退化。而对一个正常的文本做字符串匹配才是最常用的情景，而不是那种专门设计的极端情况（在真实的业务中，到底什么时候才会出现在 100万个 a 后加上一个 b 这样的字符串中，去寻找 1 万个 a 加上一个 b 这样的子串？）。所以，这里，也是在考量通用性。

这样的例子非常多。精巧地算法很多，但其实，常用的算法就那么多。大多数语言的标准库的功能是涵盖常用的算法。

至于一些极其特殊的算法，要到其他专有领域的库中去寻找。如果找不到呢？恭喜你，你发现了一个金矿，把那些你觉得有用，但是却没有一个好的库/框架涵盖的算法封装起来，很有可能将会成为一个很著名的项目呢：）

继续加油！：）

0