【算法】五分钟算法小知识：为什么要分稳定排序和非稳定排序？

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

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

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

【遇见吕老师】

【面试现场】

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

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

半分钟过去了。

【请教大神】

吕老师：笔试主要问是什么，而面试主要问为什么。

【吕老师的课】

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

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

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

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

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

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

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

【课后】

课后小史又找到吕老师。

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

来源 | 五分钟学算法

作者 | P.yh