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

分析排序算法的执行效率

1. 最好情况、最坏情况、平均情况时间复杂度
为什么要区分这三种时间复杂度呢？第一，有些排序算法会区分，为了好对比，最好都做一下区分。第二，对于要排序的数据，有的接近有序，有的完全无序。有序度不同的数据，对于排序的执行时间肯定是有影响的，要知道排序算法在不同数据下的性能表现。
2. 时间复杂度的系数、常数 、低阶
时间复杂度反应的是数据规模 n 很大的时候的一个增长趋势，所以它表示的时候会忽略系数、常数、低阶。但是实际开发中，排序的可能是 10 个、100 个、1000 个这样规模很小的数据，所以，在对同一阶时间复杂度的排序算法性能对比的时候，就要把系数、常数、低阶也考虑进来。
3. 比较次数和交换（或移动）次数
基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。所以，应该把比较次数和交换（或移动）次数也考虑进去。

排序算法的内存消耗

算法的内存消耗可以通过空间复杂度来衡量，排序算法也不例外。不过，针对排序算法的空间复杂度，还引入了一个新的概念，原地排序（Sorted in place）。原地排序算法，就是特指空间复杂度是 O(1) 的排序算法。冒泡排序、插入排序、选择排序三种排序算法，都是原地排序算法。

排序算法的稳定性

仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法，还有一个重要的度量指标，稳定性。如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。
比如有一组数据 2，9，3，4，8，3，按照大小排序之后就是 2，3，3，4，8，9。这组数据里有两个 3。经过某种排序算法排序之后，如果两个 3 的前后顺序没有改变，那就把这种排序算法叫作稳定的排序算法；如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法。
为什么要考虑是否稳定？在真正软件开发中，要排序的往往不是单纯的整数，而是一组对象，需要按照对象的某个 key 来排序。