五分鐘學演算法之經典演算法題：排序演算法（360校招筆試題）

• 2019 年 10 月 18 日
• 筆記

今天分享的一道演算法面試題來源於 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 本 演算法編程書籍。