如何衡量一个排序算法的性能

向右看齐 2023-09-27 21:08 106阅读 0赞

这是八股文的知识，但是中国人又个好的习惯，当别人给你一块好吃的面包时，你总想知道这个面包是怎么做的，对于目前的IT行业来说，不管这个做法你是被动的学习还是主动的探索，你都要知道，也必须要知道。

高端的面试，往往不会直接让你写代码（我经历过一个面试，要求纸上写一个图的数据结构，这可能和我简历中的一条**利用图的特性优化启动速度**有关，但是一般情况下，我认为这个思想重于实践，并且实践的复杂程度纸上是写不出来的），有经验的面试官会给你算法，但是重点是考虑你的思路和对模式算法套路的理解，即应用。

比如说，面试会要求说一下什么是冒泡排序，或者快速排序，并讲一下快速排序的大概过程。 为什么是这两个呢？因为二者在不同时间复杂度中都具有代表性，不知道时间复杂度怎么分析的，可以看一下 [算法-时间复杂度分析][-]

再比如，同样是O(n^2)的时间复杂度，为什么推荐使用插入排序而不推荐冒牌排序？这个问题则主要考查分析能力。

凡此种种，都逃离不了对上面“做法”的扩展。

之前在[拥有思想，你就是高级、资深、专家、架构师][Link 1] 中提到过，要提升编程思想，数据结构和算法是必不可少的环节，而今天我发现，掌握分析算法的一些分析能力更加重要，这就好比知道了怎么做面包，还会担心没有面包吗？

### 那如何分析一个排序算法呢 ###

#### 算法内存消耗 ####

也就是常说的空间复杂度，在排序算法中既有原地排序，也有创建辅助空间排序的，比如冒泡、插入等都是原地排序的，原地排序是什么呢？原地排序指空间复杂度是O(1)的排序算法。

这个指标怎么是分析一个算法的影响因素呢？ 比如相同时间复杂度的空间复杂度越小则应是我们选择的标准。

在这之前，必须要明白的一点就是算法的性能除了算法本身实现之外，都是时间和空间的转换来平衡的。

#### 排序算法的执行效率 ####

执行的效率一般讲，以下几点

*  时间复杂度（最好时间复杂度、最坏时间复杂度、平均时间复杂度）

为什么要区分这三种时间复杂度呢？

1.  有些排序算法会区分，为了好对比，所以我们最好都做一下区分。
2.  对于要排序的数据，有的接近有序，有的完全无序。有序度不同的数据，对于排序的执行时间肯定是有影响的，我们要知道排序算法在不同数据下的性能表现

*  时间复杂度的系数、常数 、低阶

时间复杂度反映的是数据规模 n 很大的时候的一个增长趋势，所以它表示的时候会忽略系数、常数、低阶。但是实际的软件开发中，我们排序的可能是 10 个、100 个、1000 个这样规模很小的数据，所以，在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来。这其实是开发中比较重要的知识点，分析算法的时候常以n做目标，实际开发中则不然。

*  比较次数和交换（或移动）次数

基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动，这些操作都是需要考虑进去的

#### 算法的稳定性 ####

在排序算法中尤为明显，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变，我们就可以说他是稳定的。反之则是不稳定的

稳不稳定又有什么关系呢？

学习排序算法的时候，都是用整数来举例，但在真正软件开发中，我们要排序的往往不是单纯的整数，而是一组对象，我们需要按照对象的某个 key 来排序

比如说，我们现在要给电商交易系统中的“订单”排序。订单有两个属性，一个是下单时间，另一个是订单金额。如果我们现在有 10 万条订单数据，我们希望按照金额从小到大对订单数据排序。对于金额相同的订单，我们希望按照下单时间从早到晚有序。对于这样一个排序需求，我们怎么来做呢？

最先想到的方法是：我们先按照金额对订单数据进行排序，然后，再遍历排序之后的订单数据，对于每个金额相同的小区间再按照下单时间排序。这种排序思路理解起来不难，但是实现起来会很复杂。

借助稳定排序算法，这个问题可以非常简洁地解决。解决思路是这样的：我们先按照下单时间给订单排序，注意是按照下单时间，不是金额。排序完成之后，我们用稳定排序算法，按照订单金额重新排序。两遍排序之后，我们得到的订单数据就是按照金额从小到大排序，金额相同的订单按照下单时间从早到晚排序的。为什么呢？

稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变。第一次排序之后，所有的订单按照下单时间从早到晚有序了。在第二次排序中，我们用的是稳定的排序算法，所以经过第二次排序之后，相同金额的订单仍然保持下单时间从早到晚有序。

![format_png][]

ok ,了解答这些分析方法之后，就可以分析算法了，下面是常见的排序算法的各种分析：

![format_png 1][]

这个表中的时间复杂度一栏，很明显最后三个排序的时间复杂度更优，但是他们并不是我们常见的排序，接下来分析一下这些特殊的算法，看看以后有没有特殊的场景能使用它。

作者：麦客奥德彪  
链接：https://juejin.cn/post/7231766211615621177

[-]: https://juejin.cn/post/7148694312031617055
[Link 1]: https://juejin.cn/post/7200944831114264637
[format_png]: https://img-blog.csdnimg.cn/img_convert/de5bd6cd0055e8ca3f7b7c19a1c9e766.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/18238c129d7b659dca087487e9a54a8d.webp?x-oss-process=image/format,png