【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?


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

【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?


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


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


【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?


【遇见吕老师】


【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?

【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?

【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?


【五分钟学算法面试现场】


【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?

【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?

【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?

【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?

【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?

【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?

【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?


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


【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?

【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?

【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?


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


【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?


半分钟过去了。


【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?

【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?

【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?

【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?


【请教大神】


【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?

【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?

【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?

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


【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?

【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?

【吕老师的课】


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


【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?


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


【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?


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


【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?


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


【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?


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


【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?


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


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


【课后】


课后小史又找到吕老师。


【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?

【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?


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





五分钟学算法面试现场是互联网侦察推出的一个新的板块,旨在回放真实的面试过程,并对面试题进行全面解析,提供多种思路,比较优劣,希望对大家的面试有所帮助。


往期回顾

【五分钟学算法面试现场】如何实现可以获取最小值的栈?

【五分钟学算法面试现场】如何判断一个数是否在40亿个整数中?


【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?




原文始发于微信公众号(互联网侦察):【五分钟学算法面试现场】为什么要分稳定排序和非稳定排序?