五分钟小知识:为什么要分稳定排序和非稳定排序?-阿里云开发者社区

开发者社区> 算法编程> 正文

五分钟小知识:为什么要分稳定排序和非稳定排序?

简介: 本文主要为大家讲解一下稳定排序和非稳定排序的相关知识。

原文链接

小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT互联网公司。
image.png

今天他去了一家互联网小巨头公司面试了。


没想到面试并不像想象中的顺利。

image.png


【遇见吕老师】

image.png
image.png
image.png


【面试现场】


image.png
image.png
image.png
image.png
image.png
image.png
image.png


小史:原始数据,a2和a4的位置都是3。对于稳定排序来说,排序后的序列,a2一定还是在a4前面。但是对于非稳定排序来说,就不一定了,可能排完序之后,a4反而在a2的前面了。

image.png
image.png
image.png


题目:既然最后都是有序序列,为什么还要分稳定和非稳定的排序呢?

image.png


半分钟过去了。

image.png
image.png
image.png
image.png


【请教大神】

image.png
image.png
image.png

吕老师:笔试主要问是什么,而面试主要问为什么。


image.png
image.png
【吕老师的课】

吕老师一上课就把问题抛了出来。

image.png



话音刚落,蛋哥就站了起来。


image.png


蛋哥:咱们每次考试完成后,都会按照分数进行排序。分高的自然就是第一名。分数相同的同学怎么办呢?那就是按照上次的分数来分高低。上次分高的排在前面。


image.png


蛋哥:这个时候就应该用稳定排序,在上次排好序的序列上,再针对这次的分数进行排序。稳定排序的结果能保证这次相同分数的人,上次分高的在前面。


image.png


蛋哥:再比如我们班的同学,已经按照学号排好序了。现在要按照身高排序。如果是稳定排序排好之后,身高相同的同学,还是按照学号顺序的。


image.png


吕老师:没错,其实就是有两个排序关键字的时候,稳定排序可以让第一个关键字排序的结果服务于第二个关键字排序中数值相等的那些数。


小史听完后,觉得很惭愧,其实这些场景自己也遇到过,早该想到的。


【课后】
课后小史又找到吕老师。
**
image.png
image.png

**
吕老师:你看的东西很多,是你学到了很多知识。但是这些知识之间的关联,需要你进行深入思考才能得到的。找到知识之间的联系,找到知识和实际场景之间的联系,多想想为什么,才能做到融会贯通。

来源 | 五分钟学算法
作者 | 程序员小吴

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接