排序总结

排序的方法非常多，先看维基百科中的一张关于排序算法的表，这里列了50多种排序方式。

维基百科排序.png

内排序和外排序的概念

内部排序：待排序记录存放在计算机随机存储器中（说简单点，就是内存）进行的排序过程。
外部排序：待排序记录的数量很大，以致于内存不能一次容纳全部记录，所以在排序过程中需要对外存进行访问的排序过程。

我们常用的排序都是再内存中进行，所以这里只讨论内排序。

常见的内排序：

排序算法.png

稳定性和复杂度：

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

算法复杂度:

算法复杂度.png

排序优缺点及使用场景

• 冒泡排序
  冒泡排序的时间复杂度贼高，只在数据量很小的情况下使用，一般用于教学。。。
• 选择排序
  选择排序的数据交换次数O(n)，比较次数O(n²)，由于交换所需CPU时间比比较所需的CPU时间多，所以选择排序比冒泡排序要快，但是时间复杂度O(n²)在所有内排序中的确是很慢的了，只适用于数据量很小的情况使用。
• 快速排序
  快速排序是对冒泡排序的一种改进。快排也有很多有方式，单轴快排和双轴快排，单轴快排还有单分双向扫描和单分三向扫描。JDK1.7以后Arrays.sort()都是用双轴快排了，这种排序方式优化了传统快速排序对大量重复数据排序效率低的缺点。
  总体来说快速排序是目前使用最多的，也是效率很高的方式，时间复杂度O(n*log2ⁿ)，数据量越大越能体现出它效率高。

eg:

部分图片和资源来源：
https://blog.csdn.net/Holmofy/article/details/70245895
https://www.cnblogs.com/onepixel/articles/7674659.html