數據結構-分析期末選擇題考點（排序）

何似清歌倚桃李

一爐沈水醉紅燈

契子??

上一期給大家提供了大概會考的題型給老鐵們復習的大致思路

這一期還會是一樣，我將整理一下排序的題型以及解題方法給你們

由于時間還很多，我就慢慢總結吧，一天一章的樣子，明天總結串、后天總結圖

然后坦然的走向期末考的刑場

?我們還是先來講一下排序吧？我對這塊比較熟

排序重點考快排的方法，分析時間復雜度、穩定性

考排序的話，快排是必考的，因為太重要了

如果快排還不懂的老鐵，可以去看看我之前的文章：手撕快排（點擊鏈接即刻跳轉）

我們二叉樹中不是還有個堆嗎？我遇到的題中往往是結合排序來考的 --?堆排序。題型大概就是初始化建堆。如果還有對堆了解還不夠深刻的老鐵，請看這篇文章：堆排序

然后其他的題型便是：給出一些排序考你穩定性以及時間復雜度了，這里稍微去翻一下課本就行

（1）快排（常考排完一次快排后的序列）大概率會考 == 必考

我說的都是有根據的，都是自己做到的作業題以及結合一些考試因素，所以可以選擇相信我

（2）堆排序（初始化建堆）高幾率

（3）時間復雜度、穩定性（感覺排序也少不了的一環）

（4）環境題 -- 給出一個案例讓你選擇最優排序（這個很少見，考對所有排序的概念理解，但是學校應該不會為難你吧，不放心的話可以看看）

排序的考點大概就是這些，考的不多大概就兩三道打底的樣子（一本正經的分析）

但是這分能撿就撿，說不定離不掛科就差這幾分呢？

廢話說完了，直接上題吧 ~

快排的模擬

我們把這一類題稱為快排的模擬，因為方法就是畫圖模擬快排的實現
以30為基準，設一組初始記錄關鍵字序列為(30,15,40,28,50,10,70)
則第一趟快速排序結果為（）
A、10，28，15，30，50，40，70
B、10，15，28，30，50，40，70
C、10，28，15，30，40，50，70
D、10，15，28，30，40，50，70
我先教老鐵們模擬一遍，在公布答案：
首先說明一下快排的常識（排序思想）吧 ~ 為了以下好講（為了照顧小白）

快排思想

任取待排序元素序列中的某元素作為?基準值?，按照該排序將待排序集合分割成兩子序列，左子序列中所有元素均?小于?基準值，右子序列中所有元素均?大于?基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止

而我們之前的方法則是雙指針思想：模擬兩個指針 left、right 分別指向首尾位置，然后 right 先找比基準小的元素，left 再找比基準大的元素，找到后交換。重復以上步驟，直到兩者相遇。在這個時候，我們的相遇點的元素與基準值進行交換這樣我們的一趟快排就結束了

（覺得很空洞的可以看我之前的博客）

但是如果我們做選擇題的話還有簡單方法，我們就不用以上方法了，我之所以提一下以上方式只是為了讓大家回顧一下快排而已，接下來我將在題目的講解中教會大家這種方法

對于模擬題的最好解法就是畫圖：

<1>根據題目的要求我們選擇 30 作為基準 key，一般都是第一個位置的元素作為基準，然后我們依舊是采用雙指針，也就是 left 指向剩余元素的起始位置，right 指向剩余元素的末尾位置，如下圖所示：

<2>我們將基準元素單獨拉出來，留有一個空缺位置，像這樣：

這個時候準備工作已經做完了，可以開始操作了

<3>我們先從右邊開始找到比基準值還要小的元素

我們找到的元素是 10，就塞到那個空缺的位置中

<4>其次我們從左邊開始找比基準值大的元素

我們找到的是 40 也塞到空缺的位置中

重復以上操作

<5>當我們的雙指針重疊時，就將 30 塞回空缺位置中

這樣我們就完成了一趟快排，實在不知道為什么這樣做的老鐵先去看一下快排吧，我這里只教方法

這道題的正確答案：B

?也不知道，大家對上題了解了多少，這里再提供一道
對數字序列28 16 32 12 60 2 5 72進行升序的快速排序（以第一個關鍵碼為基準的方法）
一次劃分后的結果為（）
A.2 5 12 16 28 60 32 72
B.2 16 5 12 28 60 32 72
C.2 16 12 5 28 60 32 72
D.5 16 2 12 28 32 60 72
我們這次干脆換一種方法吧 ~ 用我們快排的原始方法：

一開始與上面那題同理，找到基準，再固定雙指針

<1>右邊開始先找小于基準的元素，左邊再找大于基準的元素

我們找到的是 5 后，左邊在開始找

<2>數據都找到了便交換兩者的數據

<3>重復以上步驟

<4>當兩個指針相遇時，便讓當前數據與基準值 key 做交換

所以答案選擇：B

解析：

快速排序以基準值為中心，對元素進行劃分，這里?28 為基準值，則小于 28 的和大于 28 的進行交換，完成一次劃分

這樣我們的快排模擬的題型就告以段落吧，接下來我們來看看堆排序的題型

現有數字序列 5 11 7 2 3 17，目前要通過堆排序進行降序排序
那么由該序列建立的初始堆應為（）
A.2 3 7 11 5 17
B.17 11 7 2 3 5
C.17 11 7 5 3 2
D.2 3 5 7 11 17
我們先來分析一下題目，對堆還不了解的去點上面的鏈接：

這里說進行降序排序，所以我們要建小堆，每次把堆頂元素放在當前堆的最后一個位置

建堆要進行向下調整算法（從最后一個非葉子節點開始進行向下調整算法，直到根元素）

我們這里就簡單的模擬一下吧：

堆簡單來說就是二叉樹的數組表現形式，這里我們通過堆模擬一下二叉樹

然后從我們的葉子節點開始，因為我們是建立小堆，那么最小的元素肯定是排在上面的

知道這個原理我們就來開始調整

因為 2 （左孩子）比 3（右孩子）小也比 11（雙親）小

所以我們就要調整 2 與 11 的位置（根據小堆原理，最小元素排在上面）

重復上面步驟開始建堆

最后我們建堆完成后便是這個樣子：

然后轉化為我們的數組，所以初始堆序列為： 2 3 7 11 5 17

因此答案：A

?所以像這種送分題務必拿下 ~

?畫圖題基本上已經講完了，我們來看一下概念題 ~

下列排序算法中，占用輔助空間最多的是（）
A.歸并排序
B.快速排序
C.希爾排序
D.堆排序
答案：A

解析：

歸并排序空間復雜度：n

快排： logn

希爾、堆排： 1
下列關于排序方法和其平均時間復雜度，配對錯誤的是（）
A.堆排序——O(nlog2 n)
B.直接插入排序——O(n^2)
C.選擇排序——O(n^2)
D.歸并排序——O(n^2)
答案：D

解析：

歸并排序是二分排序，其實際復雜度為 nlogn
下列排序方法中，每一趟排序結束時都至少能夠確定一個元素最終位置的方法是（ ）① 選擇排序② 歸并排序③ 快速排序④ 堆排序A.①④
B.①②④
C.①③④
D.①②③④
這種題就考的是對所有排序的模擬了，需要你了解所有排序的實現原理，屬于偏難的題目，小概率會出

答案：C

解析：

（1）選擇排序每次選一個最值，放在最終的位置

（2）快速排序每次基準值的位置也可以確定

（3）堆排序每次堆頂元素的位置也可以確定

所以這三種方法都可以每次至少確定一個元素的位置

（4）歸并排序每次都需要對 n 個元素重新確定位置，所以不能保證每次都能確定一個元素位置，有可能每次排序所有元素的位置都為發生變化
下列排序方法中，哪一種是不穩定的（）
A.直接插入排序
B.歸并排序
C.選擇排序
D.冒泡排序
答案：C

解析：

（1）直接插入一般可以從前向后進行元素的插入，相同元素的相對位置可以不發生變化

（2）歸并也可以保證相對位置不變

（3）冒泡排序在元素相同的情況下也可以不進行交互，也可以保證穩定

（4）選擇排序的思想是每次選出最值，放在已排序序列的末尾，如果最值有多個，而選出的為最后一個最值，會導致相對位置發生變化
下列關于歸并排序的說法中正確的是（）
A.歸并排序不需要輔助空間
B.歸并排序的時間復雜度是O(logn)
C.歸并排序是穩定排序
D.歸并排序的操作方式類似二叉樹的前序遍歷
答案：C

解析：

（1）歸并排序需要一個輔助空間暫時保存部分區間的排序元素

（2）歸并排序是一種二分排序算法，每次都需要給 n 個元素排序，排序的過程需要 logn，即樹的高度，所以時間復雜度為 nlogn

（3）歸并排序中，相同元素的相對位置不會發生變化，所以是穩定排序