第08講 排序算法

教練：老馬的程序人生
微信：ProgrammingAssistant
博客：https://lsgogroup.blog.csdn.net/

---

講課目錄

• 常考的排序算法
• 項目制作：“三個數排序”
• 項目制作：“成績查詢”
• 項目制作：“排序”
• 項目制作：“森林運動會”

---

排序算法

• 計算機學會（GESP）中屬于四級的內容

• 電子學會（CIE）中屬于四級的內容

---

排序算法

• 交換排序（冒泡排序）
• 插入排序
• 選擇排序

---

排序算法：交換排序

思路：通過相鄰記錄之間的比較和交換

• 使關鍵字較小的記錄如氣泡一般逐漸向上漂移直至水面。
• 使關鍵字較大的記錄如重物一般逐漸向下沉降直至水底。

例如：對以下這組數字由小到大排序。

$$45,78,12,34,32$$

---

真題練習

01：隨機生成5個數字存儲到列表中，下面哪個選項可以實現列表中的數字從小到大排列？（ ）

---

• A.

---

• B.

---

• C.

---

• D.

• 參考答案：A
• 試題解析：C，D通過中間變量交換數據錯誤，由于是由小到大排序，第一趟需要把最大的數據放到最后面。選擇A。

---

真題練習

02：使用冒泡排序法對 5, 2, 6, 3, 8 進行升序排列，則第一趟排序的結果為？（　）

• A. 2, 5, 3, 6, 8
• B. 2, 5, 6, 3, 8
• C. 2, 3, 6, 5, 8
• D. 2, 3, 5, 6, 8

• 參考答案：A
• 試題解析：冒泡排，5 > 2交換，5 < 6 不交換，6 > 3 交換，6 < 8不交換。第一趟排序之后的序列2、5、3、6、8選擇A。

---

真題練習

03：使用冒泡排序算法對數據：32、40、21、46、69，進行從小到大排序，第一輪排序的結果是？（　）

• A. 32、40、21、46、69
• B. 40、32、21、46、69
• C. 21、32、40、46、69
• D. 32、21、40、46、69

• 參考答案：D
• 試題解析：冒泡排，32 < 40不交換，40 > 21 交換，40 < 46 不交換，46 < 69 不交換。第一趟排序之后的序列32、21、40、46、69，選擇D。

---

排序算法：插入排序

思路：將一個記錄插入到已經排好序的有序表中，從而得到一個新的記錄增1的有序表。即：先將序列的第1個記錄看成是一個有序的子序列，然后從第2個記錄逐個進行插入，直至整個序列有序為止。

例如：對以下這組數字由小到大排序。

$$45,78,12,34,32$$

---

排序算法：選擇排序

思路：在要排列的一組數（$n$個）中，選出最小的一個數與第1個位置的數交換；然后在剩下的數當中再找最小的與第2個位置的數交換，依次類推，直到第個$n?1$元素和第個$n$元素比較為止。

例如：對以下這組數字由小到大排序。

$$45,78,12,34,32$$

---

真題練習

04：對存有8個元素的列表 [49, 38, 65, 97, 76, 13, 27, 50] 按從小到大的順序進行排序，選擇排序第一趟的排序結果是？（ ）

• A．[13，38，65，97，76，49，27，50]
• B．[13，27，38，49，50，65，76，97]
• C．[97，76，65，50，49，38，27，13]
• D．[13，38，65，50，76，49，27，97]

• 參考答案：A
• 試題解析：選出最小的13和第一個位置上的49交換位置。第一趟排序之后的序列為[13，38，65，97，76，49，27，50]，選擇A。

---

項目制作：“三個數排序”

2022.09 編程題 三個數排序（利用交換排序）

輸入三個數，比較三個數的大小，并將這三個數按照從小到大的順序說出。

---

1. 準備工作

（1）保留小貓角色，默認位置；

（2）白色背景。

---

2. 功能實現

（1）依次詢問輸入三個數；

---

---

---

（2）按下空格鍵，小貓從小到大說出三個數，三個數之間用逗號隔開。

---

3. 評分標準

（1）使用詢問并等待輸入三個數；（3分）

（2）按下空格鍵后，小貓能夠按照從小到大的順序說出三個數（10分），格式為“X，Y，Z”（2分）。

---

項目制作：“成績查詢”

2022.06 編程題 成績查詢（利用交換排序）

期末考試結束了，小朋友想知道自己考試的成績和班級排名，讓我們一起來實現這個功能吧！

---

1. 準備工作

（1）保留默認白色背景和小貓角色；

（2）創建名為“姓名”和“成績”的列表，按照圖1輸入相關內容。

---

2. 功能實現

（1）點擊小綠旗，小貓詢問“你要查詢誰的成績？”

（2）如果輸入的姓名沒在“姓名”列表中，小貓說“此姓名無效！”2秒，如圖2，程序結束；

---

（3）如果輸入的姓名在“姓名”列表中，小貓可以根據給定的姓名，查詢出對應的成績，如圖3；

---

（4）對成績進行降序排列，并說出該成績的序號（名次），如圖4。

---

3. 評分標準

（1）正確創建列表“姓名”和“成績”(1分），只要多于三個姓名和成績即可，不一定跟題目數據一致（1分）；

（2）小貓詢問，能夠判斷姓名不在列表中情況；（3分）

（3）姓名在列表中，說出成績；（4分）

（4）對成績列表進行降序排列，需要有降序排序的過程；（4分）

（5）讓小貓說出該成績在“成績”列表的序號。（2分）

---

項目制作：“排序”

2019.12 編程題 排序（利用插入排序）

---

1. 準備工作

（1）選擇空白背景；

（2）保留小貓角色。

2. 功能實現

（1）制作一個新的積木，文字標簽為“排序”，添加三個輸入項，以便于輸入三個待排序的數字；

（2）在自定義積木的三個輸入框中，輸入任意三個數字，點擊綠旗。

（3）名稱為“排序”的列表中，將按照從大到小的順序排列。

---

項目制作：“森林運動會”

2021.12 編程題 森林運動會（利用插入排序）

在森林運動會中，小貓、小狗、小兔子、烏龜、小猴子參加了800米耐力跑項目，分別耗時3分25秒、4分15秒、3分45秒、4分45秒、4分5秒。請設計程序實現自動排名。

---

排序前

---

排序后

---

1. 準備工作

（1）保留小貓角色及空白背景；

2. 功能實現

（1）建立名為“耐力跑”的列表，用于記錄運動員的成績，以秒為單位；

（2）點擊綠旗，初始化列表，依次往列表中加入：205，255，225，285，245；

（3）點擊小貓，對運動員的成績進行降序排列。

---

3. 評分標準

（1）初始化列表，刪除所有項后，加入成績；（2分）

（2）點擊小貓后，排序降序排列正確；（5分）

（3）正確刪除、替換鏈表中的數據；（2分）

（4）正確使用循環的嵌套；（1分）