JDK排序算法实现+常见面试题自验🌟🌟🌟🌟
排序算法的最后一篇文章，我们先来看看 Java 核心类库的 Arrays.sort() 方法，用到了什么排序算法。
对于平时的工作场景中，大家大部分时间应该都是直接使用 Arrays.sort() 方法的，不过我们也可以一探究竟，重点是理解他为什么选择这些排序算法。
这里为大家解答一下，感兴趣可以具体看一下源码实现。
Arrays.sort() 方法主要是根据排序数组的不同情况使用了不同的排序算法：
- 对于对象数组，
Arrays.sort()方法结合了归并排序和插入排序，还记得我们之前在讲归并排序有说过可以利用插入排序来优化归并排序吗？ - 对于原始数据类型的数组：
Arrays.sort()方法会使用快速排序。
思考一下，为什么 Java 是这样实现的？
我认为主要有以下两点：
- Java 的标准库要服务于广泛的应用需求，因此需要一个在多种数据特性下都能有较好表现的算法。而归并排序和快速排序的时间复杂度都是 O(NlogN)，且在大多数场景下的性能都很不错。
- 某些场景下需要 稳定排序，即相等元素的原始顺序保持不变，这也影响了算法的选择。
其实我们在讲解排序算法的时候，一直在讲的一点是没有一种排序算法是完美的，每种排序算法都有其特点和适用场景，选择合适的排序算法才可以有效提高程序的性能。学习的时候重点也是理解这些算法的原理。
其实学习什么技术都是一样的，重点是要知道技术可以为我们解决什么样的问题，在解决这个问题的时候我们有哪些解决方案，每种解决方案的优劣是什么，哪种方案更适符合我们的需求。
毕竟很多大佬都说过，没有不好的技术，只有滥用技术的人。
最后，我们对所有的排序算法做一个对比。
| 排序算法 | 时间复杂度 (平均) | 时间复杂度 (最好) | 时间复杂度 (最坏) | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | ${O(n^2)}$ | O(n) | ${O(n^2)}$ | O(1) | 稳定 |
| 选择排序 | ${O(n^2)}$ | ${O(n^2)}$ | ${O(n^2)}$ | O(1) | 不稳定 |
| 插入排序 | ${O(n^2)}$ | O(n) | ${O(n^2)}$ | O(1) | 稳定 |
| 希尔排序 | O(n log n) | O(n log n) | ${O(n^2)}$ | O(1) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 快速排序 | O(n log n) | O(n log n) | ${O(n^2)}$ | O(log n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | O(k) | 稳定 |
| 基数排序 | O(nk) | O(nk) | O(nk) | O(n + k) | 稳定 |
如果忘了某种排序算法的实现，或者看完下面的问题却不知道如何回答，可以查看文章复习喔！
什么是排序算法的稳定性，内部排序和外部排序？
冒泡排序怎么优化？
选择排序是稳定排序吗，为什么？
插入排序的时间复杂度一定是 On方吗？
希尔排序为什么比插入排序的性能好？
如何优化归并排序？
你会归并排序的迭代写法吗？
如何优化快速排序？
快速排序如何优化数组有大量重复元素的场景？
计数排序的时间复杂度是多少？
基数排序为什么从元素的最低位开始排序？
堆排序的过程是怎么实现的？