阅读 146

五分钟学算法之经典算法题:排序算法(360校招笔试题)

今天分享的一道算法面试题来源于 360校园招聘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 :快速排序。

欢迎前往我的个人网站进行阅读:www.cxyxiaowu.com原文地址:https://www.cxyxiaowu.com/2536.html

❤️ 看完三件事:

如果你觉得这篇内容对你挺有启发,我想邀请你帮我三个忙:

  • 点赞,让更多的人也能看到这篇内容(收藏不点赞,都是耍流氓 -_-)
  • 关注我和专栏,让我们成为长期关系
  • 关注公众号「五分钟学算法」,第一时间阅读最新的算法文章,公众号后台回复 1024 送你 50 本 算法编程书籍。
关注下面的标签,发现更多相似文章
评论