1. 前言
排序算法是在生活中随处可见，也是算法基础
2. 算法分类
十种常见排序算法可以分为两大类：
比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
相关概念稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
选择排序的不稳定例子很简单。比如A 80 B 80 C 70 这三个卷子从小到大排序
第一步会把C和A做交换 变成C B A
第二步和第三步不需要再做交换了。所以排序完是C B A
但是稳定的排序应该是C A B
3. 十种算法比较
排序算法时间复杂度空间复杂度稳定性适用场景
冒泡排序
O(n^2)
O(1)
稳定
n较小时
选择排序
O(n^2)
O(1)
不稳定
n较小时
插入排序
O(n^2)
O(1)
稳定
基本有序时
希尔排序
O(nlogn)~O(n^2)
O(1)
不稳定
n较大时
归并排序
O(nlogn)
O(n)
稳定
n较大时
快速排序
O(nlogn)~O(n^2)
O(logn)~O(n)
不稳定
平均情况下
堆排序
O(nlogn)
O(1)
不稳定
n较大时
计数排序
O(n+k)
O(n+k)
稳定
k较小时
桶排序
O(n+k)
O(n+k)
稳定
数据分布均匀时
基数排序
O(d(n+k))
O(n+k)
稳定
d较小时
表格中的n表示数据规模，k表示桶的个数或者计数范围，d表示基数的位数。
4. 哪种排序算法最快？
这个问题没有一个确定的答案，因为不同的排序算法在不同的情况下可能有不同的表现。
一般来说，快速排序是被认为最快的排序算法，它的平均时间复杂度是O(nlogn)，但是在最坏情况下，它的时间复杂度会退化到O(n^2)。
而归并排序和堆排序也有O(nlogn)的平均时间复杂度，但是它们的最坏情况下也是O(nlogn)，所以它们比快速排序更稳定。
另外，非比较类排序如计数排序、桶排序和基数排序，在数据分布满足一定条件时，可以达到O(n)的线性时间复杂度，但是它们需要额外的空间开销，并且对数据的范围和位数有限制。
总之，要选择最快的排序算法，需要根据数据的规模、分布、范围等因素进行综合考虑。以下是一些参考资料，你可以进一步了解不同排序算法的优缺点和适用场景。
5. 十大排序算法 在 JDK 源码中有哪些应用
总结了以下几点：
JDK源码中最常用的排序算法是归并排序和快速排序，它们分别用于实现Arrays.sort()和Collections.sort()方法，对数组和集合进行排序。归并排序和快速排序都是分治法的典型应用，具有较高的时间效率，但是归并排序需要额外的空间开销，而快速排序在最坏情况下会退化为O(n^2)的时间复杂度。
JDK源码中还用到了插入排序和希尔排序，它们主要用于对小规模或基本有序的数据进行优化。插入排序和希尔排序都是基于交换元素的位置来实现排序，插入排序是稳定的，但是时间复杂度较高，希尔排序是不稳定的，但是可以减少比较和移动的次数。
JDK源码中还用到了计数排序和基数排序，它们主要用于对整数类型的数据进行排序。计数排序和基数排序都是非比较类的排序算法，它们可以达到线性时间的复杂度，但是需要额外的空间开销，并且对数据的范围和位数有限制。
JDK源码中没有用到的排序算法有冒泡排序、选择排序、堆排序和桶排序。冒泡排序和选择排序是比较低效的算法，它们需要进行大量的比较和交换操作，时间复杂度为O(n^2)。堆排序是一种利用堆结构来实现选择操作的算法，它可以达到O(nlogn)的时间复杂度，但是它不稳定，并且对缓存不友好。桶排序是一种将数据分配到多个桶中，然后对每个桶进行排序的算法，它可以达到O(n+k)的时间复杂度，但是它需要额外的空间开销，并且对数据的分布有要求。
6. 除了十大排序算法， 还有哪些经典排序算法
还有一些其他的经典排序算法，可参照 WIKI 排序算法 - 维基百科，自由的百科全书 (wikipedia.org) 例如：
7. 参考资料
十大经典排序算法 | 菜鸟教程
十大排序算法，看这篇就够了 - 知乎
十大排序算法比较_摸森堡的博客-CSDN博客
常用排序算法速度比较 - 知乎
十大经典排序算法——快速排序 - 知乎【算法】排序算法之快速排序 - 知乎
JDK源码中Arrays.sort()方法使用了哪些经典算法？ - 知乎
JDK源码解析之Collections.sort() - 简书
JDK源码解析之Arrays.sort() - 简书
JDK源码解析之Arrays.parallelSort() - 简书