如何分析排序算法
- 从时间角度看
1.1 需要考虑最好情况、最坏情况、平均情况的时间复杂度
我们分析排序算法，从时间角度分析的话，需要分析最好情况、最坏情况、平均情况的时间复杂度。因为不同的待排序数据其有序度是不同的，有些接近有序，有些接近无序，有些完全有序，有些完全无序。不同的情况，需要评估出大致的时间复杂度从而挑选合适的排序算法。
1.2 需要考虑时间复杂度的常数、系数、低阶
一般情况我们计算时间复杂度是会忽略常数、系数和低阶的，这是因为时间复杂度更多的是描述随着n的增长，其时间曲线的一个大致变化，反应的是n很大的时候，其时间复杂度会怎么变化。但是对于排序而言，我们日常工作中，大部分场景都是针对几十个、几百个或者几千个数据进行排序的，这个时候就需要将时间复杂度的常数、系数和低阶考虑进来
1.3 需要考虑算法的比较次数、交换次数
同样的时间复杂度，如果一个算法的比较次数和交换次数小于另一个算法，那这个算法在实际使用时的表现一般也会优于另一个算法（前提是排序算法是基于比较的） - 从空间角度
分析算法的时候，一定也要考虑内存的消耗，针对大量数据的排序，内存消耗大的算法就很有可能内存溢出。其中我们将空间复杂度为O(1)的排序算法称为原地排序 - 从稳定性角度
这里的稳定性是指数据位序的稳定性，例如针对数据：4，2，3，1，3，5而言其排序后的结果为1，2，3，3，4，5。对于稳定的排序算法而言，两个三的前后顺序是不会发生变化的。可能这里很多同学会认为3的次序发生变化有什么影响吗？对于这个例子而言确实没有什么影响，但是实际场景中，我们可能是针对一个复杂的对象进行排序的。例如：
我们需要对我们一年的消费账单进行排序，按金额倒序，然后金额一致的按账单的消费时间正序。
对于不稳定排序算法而言，按金额倒序之后，需要再对金额相同的数据按时间排序，这其实很繁琐的一个步骤，但是对于稳定排序算法而言，只需要先将数据按消费时间正序排列之后，再按金额倒序即可实现。
网友评论