GCSE 計算機科學/排序演算法

排序演算法是所有 GCSE 計算機科學課程的一部分。即使課程不需要知道以下排序演算法中的一種或多種的名稱和定義，也需要能夠在特定情況下理解和使用這些演算法。

氣泡排序

哪些課程？ AQA 3.1.4，Ed 1.1.8，OCR 2.1

氣泡排序是一種排序演算法，它不斷地遍歷一個列表，交換專案，直到它們按正確的順序出現。

氣泡排序是一種簡單的排序演算法，它的工作原理是反覆遍歷要排序的列表，比較每一對元素，如果它們順序錯誤就交換它們。重複遍歷列表，直到不需要交換，這表明列表已經排序。該演算法之所以得名，是因為較大的元素會“冒泡”到列表的頂部。這是一種非常慢的排序資料方法，在工業中很少使用。還有更快排序演算法，比如插入排序，我們將在後面討論。

逐步示例

讓我們以數字陣列“5 1 4 2 8”為例，使用氣泡排序演算法將陣列從最小數字排序到最大數字。在每一步中，以粗體顯示的元素正在被比較。

第一遍
( 5 1 4 2 8 ) $\to$ ( 1 5 4 2 8 ), 這裡，演算法比較了前兩個元素，並交換了它們，因為 5 > 1
( 1 5 4 2 8 ) $\to$ ( 1 4 5 2 8 ), 然後比較了第二個和第三個元素，並交換了它們，因為 5 > 4
( 1 4 5 2 8 ) $\to$ ( 1 4 2 5 8 ), 交換，因為 5 > 2
( 1 4 2 5 8 ) $\to$ ( 1 4 2 5 8 ), 現在，由於這些元素已經按順序排列（8 > 5），演算法不會交換它們。
演算法已經到達數字列表的末尾，最大數字 8 已經冒泡到頂部。現在它重新開始。

第二遍
( 1 4 2 5 8 ) $\to$ ( 1 4 2 5 8 ), 不需要交換
( 1 4 2 5 8 ) $\to$ ( 1 2 4 5 8 ), 交換，因為 4 > 2
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 ), 不需要交換
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 ), 不需要交換
現在，陣列已經排序，但我們的演算法不知道它是否完成了。演算法需要一個完整的遍歷，沒有任何交換才能知道它已經排序。
第三遍
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
最後，陣列被排序，演算法可以終止。

練習

1) Sort the following lists using a bubble sort. How many passes are needed?

(a) 按字母順序排序

Henry, Cat, George, Mouse

答案

Cat, George, Henry, Mouse (Pass 1)
Cat, George, Henry, Mouse (Pass 2)
2 passes

(b) 按字母順序排序

G, C, N, A, P, C

答案

C, G, A, N, C, P (Pass 1)
C, A, G, C, N, P (Pass 2)
A, C, C, G, N, P (Pass 3)
A, C, C, G, N, P (Pass 4)
4 passes

(c) 按數字順序排序

12, 56, 0, 23, 10

答案

12, 0, 23, 10, 56 (Pass 1)
0, 12, 10, 23, 56 (Pass 2)
0, 10, 12, 23, 56 (Pass 3)
0, 10, 12, 23, 56 (Pass 4)
4 passes

2) 顯示以下兩遍之後的排序結果

(a) 按字母順序排序

Emu, Shrike, Gull, Badger 

答案

Emu, Gull, Badger, Shrike (Pass 1)
Emu, Badger, Gull, Shrike (Pass 2)

(b) 按數字順序排序

99, 45, 32, 56, 12

答案

45, 32, 56, 12, 99 (Pass 1)
32, 45, 12, 56, 99 (Pass 2)

插入排序

哪些課程？ AQA 3.1.4，Ed 1.1.8，OCR 2.1

插入排序的示例。檢查每個元素並將它們按正確順序放入已排序的列表中。

不幸的是，氣泡排序是一種非常慢的排序資料方法，在工業中很少使用。我們現在將介紹一種更快的演算法，插入排序。

插入排序 是一種簡單的排序演算法：一種比較排序，其中排序後的陣列（或列表）一次構建一個條目。對於大型列表來說，它比更高階的演算法（例如下面將介紹的歸併排序）效率要低得多。但是，插入排序具有一些優勢

• 實現簡單
• 對小型資料集效率高
• 執行時使用固定數量的記憶體

插入排序需要使用兩個陣列，一個有序，一個無序。演算法的每次重複都將一個專案從無序列表移動到有序列表中的排序位置，直到無序列表中沒有元素。

排序通常是在原地進行的，不需要額外的記憶體。經過k次迭代後的結果陣列具有以下屬性：前k + 1個條目已排序。在每次迭代中，輸入的第一個剩餘條目被刪除，插入到結果中的正確位置，從而擴充套件結果

變為

每個大於x的元素在與x比較時被複制到右側。

對一個 30 元素陣列進行插入排序的動畫。請注意，有序陣列（左側）如何慢慢地消耗無序陣列（右側），直到整個資料集被排序

示例：插入排序 下表顯示了對序列 {5, 7, 0, 3, 4, 2, 6, 1} 進行排序的步驟。對於每次迭代，插入元素移動的位置數都顯示在括號中。總共 17 步。 5 7 0 3 4 2 6 1 (0) 5 7 0 3 4 2 6 1 (0) 0 5 7 3 4 2 6 1 (2) 0 3 5 7 4 2 6 1 (2) 0 3 4 5 7 2 6 1 (2) 0 2 3 4 5 7 6 1 (4) 0 2 3 4 5 6 7 1 (1) 0 1 2 3 4 5 6 7 (6) 5 7 0 3 4 2 6 1 (0) 5 7 0 3 4 2 6 1 (0) 0 5 7 3 4 2 6 1 (2) 0 3 5 7 4 2 6 1 (2) 0 3 4 5 7 2 6 1 (2) 0 2 3 4 5 7 6 1 (4) 0 2 3 4 5 6 7 1 (1) 0 1 2 3 4 5 6 7 (6)

練習：插入排序 描述插入排序的過程 答案 插入排序是一種簡單的排序演算法：一種比較排序，其中排序後的陣列（或列表）一次構建一個條目。 顯示插入排序如何在以下無序陣列上工作 9 6 7 1 2 答案 左側排序部分用下劃線表示 9 6 7 1 2 6 9 7 1 2 6 7 9 1 2 1 6 7 9 2 1 2 6 7 9 顯示插入排序如何在以下無序陣列上工作 G K L A J 答案 左側排序部分用下劃線表示 G K L A J G K L A J G K L A J A G K L J A G J K L

歸併排序

哪些課程？ OCR 2.1