开发

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

广告
广告

微信扫一扫,分享到朋友圈

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

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

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

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

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

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

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

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

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

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

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

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

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

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

我还没有学会写个人说明!

尴尬了!四分之三的Sybase/ASE用户无意迁往SAP HANA

上一篇

除了5G,华为还有Wi-Fi 6

下一篇

你也可能喜欢

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

长按储存图像,分享给朋友

ITPUB 每周精要将以邮件的形式发放至您的邮箱


微信扫一扫

微信扫一扫