1、算法分类

常见排序算法可以分为两大类：

1. 非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。
2. 线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。

2、算法复杂度

3、相关概念

稳定：如果a原本在b前面，而a==b，排序之后a仍然在b的前面。

不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。

时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。

空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

4、各种排序算法适用情况

（1）冒泡排序和选择排序：适用于数据量较小或者有部分数据已经做过排序的情况；

（2）插入排序和希尔排序：适用于大部分数据已经做过排序的情况或者已排序的数据库新增数据后再进行排序；

（3）归并排序和堆排序：时间复杂度始终是O（n*logn）。归并排序的最大好处是在数据呈现最坏情况时，是所有排序算法中表现最好的；

（4）快速排序：排序效率在同为O（n*logn）的几种排序方法中效率较高，因此经常被采用。

（5）桶排序和基数排序：对于数据为较小的整数且数据都在某一个范围内时，使用桶排序和基数排序效率较高，最好情况下时间复杂度为O（n）。