算法基础：排序算法：7个常用的衡量指标

我不是女神ヾ 2022-12-18 05:53 164阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]  
时间复杂度和空间复杂度是衡量算法的重要指标，对于排序算法这一特定算法，这篇文章整理了一些常见的基础性的指标，后续将以此为基础进行进一步的解释。

--------------------

### 文章目录 ###

*  时间复杂度
 *  空间复杂度
 *  稳定性
 *  最优时间复杂度
 *  最差时间复杂度
 *  比较次数
 *  交换次数
 *  参考内容

--------------------

# 时间复杂度 #

>  *  时间复杂度：在满足n足够大的前提下，上述常见的算法时间复杂度由小到大依次为：Ο(1)＜ Ο(log2n)＜ Ο(n)＜ Ο(nlog2n)＜ Ο(n2)＜ Ο(n3)＜ Ο(nk) ＜ Ο(2n) ，随着问题规模 n 的不断增大，时间复杂度不断增大，算法的执行效率越低

详细可参看：[https://blog.csdn.net/liumiaocn/article/details/108087625][https_blog.csdn.net_liumiaocn_article_details_108087625]

# 空间复杂度 #

>  *  空间复杂度：算法使用的存储空间大小和输入规模之间的关系，在满足n足够大的前提先，空间复杂度能够在一定程度上显示算法对于存储的使用效率。

详细可参看：[https://blog.csdn.net/liumiaocn/article/details/108087625][https_blog.csdn.net_liumiaocn_article_details_108087625]

--------------------

# 稳定性 #

>  *  稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r\[i\]=r\[j\]，且r\[i\]在r\[j\]之前，而在排序后的序列中，r\[i\]仍在r\[j\]之前，则称这种排序算法是稳定的；否则称为不稳定的。比如正常的冒泡排序是稳定的，但是如果将冒泡升序排序的算法中的>改为>=，则会由稳定排序算法变为不稳定排序算法。

# 最优时间复杂度 #

>  *  最优时间复杂度：时间复杂度一般是一个平均的时间复杂度，而最优时间复杂度则是指所有情况都利于提升排序速度的情况下，最优的情况下，当前算法所能到的算法效率，能够在一定程度上说明此算法的潜力。

# 最差时间复杂度 #

>  *  最差时间复杂度：时间复杂度一般是一个平均的时间复杂度，而最差时间复杂度则是指所有情况都不利于提升排序速度的情况下，最差的情况下，当前算法所可能的算法效率，能够在一定程度上说明此算法受外界影响的风险程度。

# 比较次数 #

>  *  比较次数：比较是排序的重要操作，比较次数本身也能直接地反应排序算法的复杂程度和效率，平均比较次数、最优比较次数和最差比较次数能够在一定程度上反应算法的一些特点。

# 交换次数 #

>  *  交换：交换也是排序的重要操作，交换次数本身也能直接地反应排序算法的复杂程度和效率，平均交换次数、最优交换次数和最差交换次数能够在一定程度上反应算法的一些特点。

# 参考内容 #

https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E7%A8%B3%E5%AE%9A%E6%80%A7/9763250?fr=aladdin

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/dc5c969bf39e4ae9bb87ad78093b9c7e.png
[https_blog.csdn.net_liumiaocn_article_details_108087625]: https://blog.csdn.net/liumiaocn/article/details/108087625