如果我问你:排序算法的「稳定性」有何意义?你怎么回答?

举报
G-washington 发表于 2019/10/28 23:34:37 2019/10/28
【摘要】 除了基本的实现之外,我们关注排序算法的同时,往往还会关注它的时间复杂度和空间复杂度。在面试之前,我们可能还会临时抱佛脚的去记一下其稳定性。下表中列举了几种常见的排序算法的核心总结。

虽然我们在工作不一定经常去写排序算法,但是排序算法却是充斥着我们的程序生活,比如你不经意间调用了SDK中的某个sort算法,其背后无非是什么快排、归并等算法。而且在我们面试的过程中也会经常被问及,如果你在面试的过程中连一个最基本的冒泡排序都不会写的话,那么很明显的面试结果也不会好到哪里去。

除了基本的实现之外,我们关注排序算法的同时,往往还会关注它的时间复杂度和空间复杂度。在面试之前,我们可能还会临时抱佛脚的去记一下其稳定性。下表中列举了几种常见的排序算法的核心总结。

640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1

对于时间复杂度和空间复杂度这种倒是好理解,如果你经常刷leetcode,就会非常关注此类问题。但是「稳定性」这个属性往往被我们所忽视,我们一般会记住稳定性的定义以及特定算法所对应的稳定性,但是是否想过「稳定性」有何意义?

稳定性的定义:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。

如果我们只是面对简单的数字排序,那么稳定性确实也没有多大意义。比如,1 2 3 3 4的序列中如果第一个3和第二个3在sort方法反复执行之后位置也反复变化,但是对于调用sort方法所想要获得排序结果的上游应用而言,那么结果还是1 2 3 3 4,至于3的次序,无关紧要。

如果排序的内容仅仅是一个复杂对象的某一个数字属性,那么稳定性依旧将毫无意义(所谓的交换操作的开销已经算在算法的开销内了,如果嫌弃这种开销,不如换算法好了?

如果要排序的内容是一个复杂对象的多个数字属性,但是其原本的初始顺序毫无意义,那么稳定性依旧将毫无意义。

那么排序算法的「稳定性」在什么情况下才会变得有意义呢?

举个例子,一个班的学生已经按照学号大小排好序了,我现在要求按照年龄从小到大再排个序,如果年龄相同的,必须按照学号从小到大的顺序排列。那么问题来了,你选择的年龄排序方法如果是不稳定的,是不是排序完了后年龄相同的一组学生学号就乱了,你就得把这组年龄相同的学生再按照学号拍一遍。如果是稳定的排序算法,我就只需要按照年龄排一遍就好了。

从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。要排序的内容是一个复杂对象的多个数字属性,且其原本的初始顺序存在意义,那么我们需要在二次排序的基础上保持原有排序的意义,才需要使用到稳定性的算法。

排序算法的「稳定性」有何意义?这个还是要分应用场景来看,很多使用情况下,并没有什么实质的意义,而在有些情况下却有很重要的意义。

有很多算法你现在看着没啥,但是当放在大数据云计算的条件下它的稳定性非常重要。举个例子来说,对淘宝网的商品进行排序,按照销量,价格等条件进行排序,它的数据服务器中的数据非常多,因此,当时用一个稳定性效果不好的排序算法,如堆排序、shell排序,当遇到最坏情形,会使得排序的效果非常差,严重影响服务器的性能,影响到用户的体验。

排序算法的「稳定性」有何意义?你以前是否忽略了这个问题,那么现在你Get到了吗?或者你有更好的答案,欢迎在文末留言。


640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1



想知道更多?描下面的二维码关注我


640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1



怎么加群?:>>>Learn More<<

怎么免费加入知识星球:>>>Free<<<

免费资料入口:后台回复“666”

内推通道>>>>

本文转载自微信公众号朱小厮的博客

原文链接:https://mp.weixin.qq.com/s/wm9GfLKtUQtLxfolTNpmhQ

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。