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

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

原文链接

小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进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

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

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

目录
打赏
0
0
0
0
58
分享
相关文章
班里新来的交换生
班里新来的交换生
107 0
剥开比原看代码04:如何连上一个比原
作者:freewind 比原项目仓库: Github地址:https://github.com/Bytom/bytom Gitee地址:https://gitee.com/BytomBlockchain/bytom 在上一篇我们已经知道了比原是如何监听节点的p2p端口,本篇就要继续在上篇中提到的问题:我们如何成功的连接上比原的节点,并且通过身份验证,以便后续继续交换数据? 在上一篇中,我们的比原节点是以solonet这个chain_id启动的,它监听的是46658端口。
1182 0
剥开比原看代码15:比原是如何转帐的
作者:freewind 比原项目仓库: Github地址:https://github.com/Bytom/bytom Gitee地址:https://gitee.com/BytomBlockchain/bytom 在前面几篇中,我们做了足够了准备,现在终于可以试一试转帐功能了! 这里的转帐最好使用solonet,再按前一篇文章的办法修改代码后产生单机测试币,然后再试。
1317 0
剥开比原看代码05:如何从比原节点拿到区块数据?
作者:freewind 比原项目仓库: Github地址:https://github.com/Bytom/bytom Gitee地址:https://gitee.com/BytomBlockchain/bytom 在前一篇中,我们已经知道如何连上一个比原节点的p2p端口,并与对方完成身份验证。
1202 0
剥开比原看代码03:比原是如何监听p2p端口的
作者:freewind 比原项目仓库: Github地址:https://github.com/Bytom/bytom Gitee地址:https://gitee.com/BytomBlockchain/bytom 我们知道,在使用bytomd init --chain_id mainnet/tes...
1506 0
剥开比原看代码02:比原启动后去哪里连接别的节点
作者:freewind 比原项目仓库: Github地址:https://github.com/Bytom/bytom Gitee地址:https://gitee.com/BytomBlockchain/bytom 比原启动后去哪里连接别的节点 最开始我对于这个问题一直有个疑惑:区块链是一个分布式的网络,那么一个节点启动后,它怎么知道去哪里找别的节点从而加入网络呢? 看到代码之后,我才明白,原来在代码中硬编码了一些种子地址,这样在启动的时候,可以先通过种子地址加入网络。
1383 0
剥开比原看代码14:比原的挖矿流程是什么样的?
作者:freewind 比原项目仓库: Github地址:https://github.com/Bytom/bytom Gitee地址:https://gitee.com/BytomBlockchain/bytom 当我们以bytom init --chain_id=solonet建立比原单机节点用于本地测试时,很快会发现自己将面临一个尴尬的问题:余额为0。
1373 0
剥开比原看代码06:比原是如何把请求区块数据的信息发出去的
作者:freewind 比原项目仓库: Github地址:https://github.com/Bytom/bytom Gitee地址:https://gitee.com/BytomBlockchain/bytom 在前一篇中,我们说到,当比原向其它节点请求区块数据时,BlockKeeper会发送一个BlockRequestMessage把需要的区块height告诉对方,并把该信息对应的二进制数据放入ProtocolReactor对应的sendQueue通道中,等待发送。
1156 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等