根据时间复杂度可以把常用的排序算法区分为三类

排序算法 时间复杂度 是否基于比较
冒泡、插入、选择 $$O(n^2)$$ 是
快排、归并 $$O(nlogn)$$ 是
桶、计数、基数 $$O(n)$$ 否

如何分析一个“排序算法”？

排序算法的执行效率

排序算法执行效率的分析，我们一般会从这几个方面来衡量：

1. 最好情况、最坏情况、平均情况时间复杂度
为什么要区分这三种时间复杂度呢？
第一，区分排序算法，容易对比。
第二，对于要排序的数据，有的接近有序，有的完全无序。有序度不同的数据，对于排序的执行时间肯定是有影响的，我们要知道排序算法在不同数据下的性能表现。

2. 时间复杂度的系数、常数 、低阶
时间复杂度反应的是数据规模 n 很大的时候的一个增长趋势，n 规模很大时，会忽略系数、常数、低阶。

在对同一阶时间复杂度的排序算法性能对比的时候，需要把系数、常数、低阶也考虑进来。

3. 比较次数和交换（或移动）次数
基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。

所以，我们在分析排序算法执行效率的时候，要把比较次数和交换（或移动）次数也考虑进去。

排序算法的内存消耗

算法的内存消耗可以通过空间复杂度来衡量。

原地排序算法（Sorted in place），是特指空间复杂度是 O(1) 的排序算法。

排序算法的稳定性

在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，则称为稳定的排序算法，反之，则为不稳定的排序算法。