找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

经典算法题:排序算法

admin 2019-11-5 21:46 92人围观 C++相关

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

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



作者 | 程序员小吴

来源公众号 | 五分钟学算法

今天分享的一道算法面试题来源于 某零2015届技术类笔试题 。

题目描述


用某种排序方法对关键字序列(25,84,21,47,15,27,68,35,20)进行排序,序列的变化情况采样如下:
20,15,21,25,47,27,68,35,84
15,20,21,25,35,27,47,68,84
15,20,21,25,27,35,47,68,84

请问采用的是以下哪种排序算法()

A. 选择排序

B. 希尔排序

C. 归并排序

D. 快速排序

题目解析


这道题目很好的考察了大家对排序方法过程的理解程度。

对于题目给出的四个选项,很容易就能排除 选择排序,因为对于 选择排序 而言它的操作是 第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。
20,15,21,25,47,27,68,35,84

序列中 20 不是最小的记录,故排除 选择排序。

接下来的三个选项实际上挺难抉择的,我们首先来回顾一下它们三个的动画。


希尔排序



归并排序



快速排序

对于 希尔排序 而言,需要知道 增量 ,根据动画我们可以理解为 gap = 4  。

先分为四组。
25 15
84 27
21 68
47 35

对这四组分别进行插入排序,加上剩下的 20 变成了
15 27 21 35 25 84 68 47 20

与题目给出的步骤不同,故排除 希尔排序。

再来看归并排序动画,逻辑操作就简单了。

先一分为二。
25,84,21,47,15,27,68,35,20

变成了
25,84,21,47


15,27,68,35,20

第二步应该是(这里与动画稍许不同,没有切分到底)
15 25 27 68 35 20 84 21 47

与题目给出的步骤不同,故排除 归并排序。

所以,答案选 D :快速排序。

问题来了,你知道标定点是哪个数字吗?可以留言说说哟。
---以上,便是今日分享,觉得不错,还请点个在看,谢谢~推荐阅读:有了这套模板,女朋友再也不用担心我刷不动 LeetCode 了
图解 LeetCode 第 421 题:数组中两个数的最大异或值
互联网人职业发展之路:三年升高工,七年做架构,十年送外卖



点击「阅读原文」,访问小吴的个人博客,在电脑端阅读 200 多篇原创算法文章!

----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:五分钟学算法,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......