五分钟学算法之经典算法题：排序算法（360校招笔试题）

清疚 2023-06-13 09:09 102阅读 0赞

今天分享的一道算法面试题来源于 **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* 不是最小的记录，故排除 **选择排序**。

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

![v2-80d1ed88443b9c2f33c245c1caa1a308\_b.gif][v2-80d1ed88443b9c2f33c245c1caa1a308_b.gif]

![v2-91c7b761b0a6c7c17d2b9d9e7dfd41ad\_b.gif][v2-91c7b761b0a6c7c17d2b9d9e7dfd41ad_b.gif]

![v2-61d3025ffec8f41e9077a3e730e52367\_b.gif][v2-61d3025ffec8f41e9077a3e730e52367_b.gif]

对于 **希尔排序** 而言，需要知道 *增量* ，根据动画我们可以理解为 `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 ：快速排序。

推荐在我的个人博客进行阅读：

[经典算法题：排序算法（360校招笔试题）-五分钟学算法][360_-]

**我的专栏：**

[和程序员小吴一起学算法][Link 1]

**❤️ 看完三件事：**

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

1.  **点赞，**让更多的人也能看到这篇内容（**收藏不点赞，都是耍流氓 -\_-**）
2.  **关注我和专栏，**让我们成为长期关系
3.  **关注公众号「五分钟学算法」，**第一时间阅读最新的算法文章，公众号后台回复 1024 送你 50 本 算法编程书籍。

![v2-7d84a7f4361bd5f8d21b98b9edb0b1b4\_b.jpg][v2-7d84a7f4361bd5f8d21b98b9edb0b1b4_b.jpg]

[v2-80d1ed88443b9c2f33c245c1caa1a308_b.gif]: https://img-blog.csdnimg.cn/img_convert/b0f7fa4a20f6f9ba7a0447fa0809abea.gif
[v2-91c7b761b0a6c7c17d2b9d9e7dfd41ad_b.gif]: https://img-blog.csdnimg.cn/img_convert/eef3e0a2899219f8d4118c5516c833d2.gif
[v2-61d3025ffec8f41e9077a3e730e52367_b.gif]: https://img-blog.csdnimg.cn/img_convert/6825b8a08963cd19a7b56f668eb4c0e1.gif
[360_-]: https://link.zhihu.com/?target=https%3A//www.cxyxiaowu.com/2536.html
[Link 1]: https://zhuanlan.zhihu.com/c_1039097450233057280
[v2-7d84a7f4361bd5f8d21b98b9edb0b1b4_b.jpg]: https://img-blog.csdnimg.cn/img_convert/cfb13222504ffb992caf217eb0c122a5.png