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

点击蓝色“五分钟学算法”关注我哟

加个“星标”,天天中午 12:15,一起学算法

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

作者 | channingbreeze

来源 | 互联网侦察


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

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


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


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


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


【遇见吕老师】


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

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

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


【面试现场】


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

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

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

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

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

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

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


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


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

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

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


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


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


半分钟过去了。


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

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

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

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


【请教大神】


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

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

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

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


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

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

【吕老师的课】


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


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


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


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


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


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


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


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


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


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


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


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


【课后】


课后小史又找到吕老师。


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

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


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


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

有热门推荐👇


1.程序员有了这套模板,女朋友再也不用担心我刷不动 LeetCode 了

2.【GitHub我在 GitHub 上看到了一个丧心病狂的开源项目!

3.【算法动画:七分钟理解什么是KMP算法

4.【数据结构十大经典排序算法动画与解析,看我就够了!


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

▼ 点击『阅读原文』查看小吴的博客

原文始发于微信公众号(五分钟学算法):五分钟小知识:为什么要分稳定排序和非稳定排序?

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 五分钟小知识:为什么要分稳定排序和非稳定排序?

我还会在以下平台发布内容

GitHub 哔哩哔哩