5. 串列的排序

串列的排序

1. 串列元素由小到大排列

串列的元素,可以按資料值由小到大的排列方式,重新安排元素順序。語法為:

串列名稱.sort()

[例] 建立串列名稱score,再對該串列的元素做由小到大的排序。 (檔名:sort.py)

程式碼: sort.py

score = [72, 98, 86, 76, 63]
# 就地修改（In-place）」，它不會回傳任何值
score.sort()
print(score)  # 印出 [63, 72, 76, 86, 98] 
```

2. 串列元素反轉排列

串列的元素,可以按反方向重新排列元素的順序。語法為:

串列名稱.reverse()

[例] 建立串列名稱animal,再對該串列的元素做由反轉排列。(檔名:reverse.py)

程式碼: reverse.py

animal=['dog','cat','monkey','fox','tiger']
animal.reverse()
print(animal)  # 印出 ['tiger', 'fox', 'monkey', 'cat', 'dog']

說明
串列元素若先以sort()方法做由小到大的排序,再以reverse()方法做反轉排列,就可以做到對串列元素做由大到小的排序。

3. 複製串列排序

使用sort()方法排序串列,是採就地排序方式(In-place）,串列經排序後會失去原有的排列順序。若要有排序後的結果,又要保有排序前的原貌,就得使用sorted()函式來複製串列並排序。

語法為:

串列名稱2 = sorted(串列名稱1,reverse=True|False)

「串列名稱1」代表排序前的原串列,「串列名稱2」代表排序後的串列。
若reverse=True,進行由大到小排序;若reverse=False,進行由小到大排序。

[例] 建立串列名稱 animal,對animal串列的元素做由小到大的排序,排序結果複製給data串列,而animal留有原順序的排列。(檔名:sorted.py)

程式碼 sorted.py

animal = ['dog','cat','monkey','fox','tiger']
data = sorted(animal, reverse = False)
print(f'animal = {animal}') # animal=['dog','cat','monkey','fox','tiger']
print(f'data = {data}')    # data = ['cat','dog','fox','monkey','tiger']

4. 氣泡排序法

使用sort()方法排序串列，固然很方便，但無法得窺串列元素間依序排列的原理及完整過程。在各種程式語言所使用的串列(陣列)元素的排序方法中，以氣泡排序法最常見。

氣泡排序法(Bubble Sort)又稱交換排序法，原理是從第一筆資料開始，逐一比較相鄰兩筆資料，如果兩筆大小順序有誤則做交換，反之則不動，接者再進行下一筆資料比較，所有資料比較完第1回合後，可以確保最後一筆資料是正確的位置。

下面利用4, -15, 20, 13, -6 由小到大排序。

n = 5  
第1回合比較了4次，n-1次  
第2回合比較了3次，n-2次  
第3回合比較了2次，n-3次  
第4回合比較了1次，n-4次  
總共比較了4回合，n-1回合

(n-1) + (n-2) + .... + 1 = n(n-1) / 2
平均時間複雜度為: O(n²)

補充說明
排序演算法的「排列次數（回合數）」與「比較次數」時，通常會以 長度為 $n$ 的串列（以你舉的例子， $n = 5$ ）來計算。

以下為你列出其他 4 種最常見排序法的分析（同樣以 $n = 5$ 個元素 來舉例說明）：

選擇排序法 (Selection Sort)

原理：每一輪從未排序的部分找出最小值，放到最前面。

排列次數（外層回合數）： $n - 1$ 次（ $5 - 1 = 4$ 次）

比較次數：無論資料原始狀態如何，固定為 $\frac{n ( n - 1 )}{2}$ 次

第 1 回合比較 4 次，第 2 回合 3 次，第 3 回合 2 次，第 4 回合 1 次。

$n = 5$ 時：共 $4 + 3 + 2 + 1 = 10$ 次。

插入排序法 (Insertion Sort)

原理：像摸撲克牌一樣，將新牌插入到已排好序的適當位置。

排列次數（外層回合數）： $n - 1$ 次（ $5 - 1 = 4$ 次）

比較次數：會根據資料原本的排序狀態而不同

最好狀況（已排好序）：只需比較 $n - 1$ 次（ $n = 5$ 時為 4 次）。

最壞狀況（完全反向）：比較 $1 + 2 + 3 + 4 = 10$ 次。

平均狀況：約為最壞狀況的一半，約 5 次。

快速排序法 (Quick Sort)

原理：選定一個基準值（Pivot），將小於它的放左邊、大於它的放右邊，再用遞迴處理左右兩邊。

排列次數（分割層數）：

最好/平均： $lo g_{2} n$ 層（ $n = 5$ 時約 2~3 層）。

最壞： $n - 1$ 次（ $5 - 1 = 4$ 次）。

比較次數：

平均 / 最好狀況：約 $n lo g_{2} n$ 次（ $n = 5$ 時約 11~12 次）。

最壞狀況（例如原本就已排好序）： $\frac{n ( n - 1 )}{2}$ 次（ $n = 5$ 時為 10 次）。

合併排序法 (Merge Sort)

原理：採用「分治法（Divide and Conquer）」，將串列對半拆解到最小單位後，再邊合併邊排序。

排列次數（拆分與合併層數）： $lo g_{2} n$ 層（ $n = 5$ 時為 3 層）。

比較次數：

無論最好或最壞，比較次數相當穩定，約為 $n lo g_{2} n$ 次。

$n = 5$ 時：約為8~9次。

種常見排序法綜合對照表（以 $n$ 個元素為例）

排序演算法|排列次數 (回合/層數)|最壞比較次數 (n=5)|平均比較次數 (n=5)|最佳比較次數 (n=5)
—|—|—|—|—
氣泡排序 (Bubble)|n - 1|10 次|10 次|4 次(經優化後)
選擇排序 (Selection)|n - 1|10 次|10 次|10 次|
插入排序 (Insertion)|n - 1|10 次|~5 次|4 次
快速排序 (Quick)| $lo g_{2} n \sim n - 1$ |10 次|~11 次|~8 次
合併排序 (Merge)| $lo g_{2} n$ |~9 次|~8 次|~5

觀念整理：

當資料量很小（如 $n = 5$ ）時，各演算法的比較次數差異不大。

但當資料量變大（如 $n = 1000$ ）時，快速排序與合併排序（ $O (n lo g n)$ ）的比較次數會遠少於氣泡、選擇、插入排序（ $O (n^{2})$ ）！

相關主題與延伸閱讀

4. 串列的函式與方法：sort()、sorted() 是串列方法與函式的延伸應用。
1. for 迴圈：氣泡排序法使用巢狀 for 迴圈實作。
4. 巢狀迴圈與無窮迴圈：氣泡排序法是巢狀迴圈的典型應用範例。
2. 一維串列：排序操作的對象即為一維串列。

以 a = [4, -15, 20, 13, -6] 整數串列為例，說明遞增排列的氣泡排序法原理，如下：

第一次排列：
串列5個元素中，兩相鄰元素值互相比較，比較後小者放前面、大者放後面，共比較4次，最後找出最大數20放至最後面的a[4]元素內。
第二次排列：
前面4個元素中，兩相鄰元素值互相比較，比較後小者放前面、大者放後面，共比較3次，最後找出第二大數13放至倒數第二個的a[3] 元素內。
第三次排列：
前面3個元素中，兩相鄰元素值互相比較，比較後小者放前面、大者放後面，共比較2次，找出第三大數4會被放至 a[2] 元素內。
第四次排列：
前面2個元素中，兩相鄰元素值互相比較，比較後小者放前面、大者放後面，共比較1次，其第四大數 -6 會被放至 a[1] 元素內，而最小的數會被放至 a[0] 元素內。

[簡例] 將 a=[4,-15,20,13,-11]整數串列,使用氣泡排序法由小到大遞增逐次排列,並顯示驗證每一次排列的結果。檔案: bubble.py

bubble.py

# 初始化待排序的整數串列（陣列），共 5 個元素
a = [4, -15, 20, 13, -11]
# 印出標題提示「排序前：」，end = '' 表示列印完後不換行，繼續接在同一行
print('排  序  前 : ', end = '')
# 使用 for 迴圈印出排序前的初始陣列內容 
# range(5) 會產生索引值 0, 1, 2, 3, 4
for i in range(5):
     # 格式化輸出：i 為索引號，a[i]:3d 表示將數值靠右對齊並佔據至少 3 個字元寬度 
     # end = ' ' 表示每個元素之間用兩個空格隔開，不換行
     print(f' a[{i:d}]={a[i]:3d}', end = '  ') # a[0]= 4 a[1]=-15 a[2]= 20 a[3]= 13 a[4]=-11
 
# 外層迴圈：控制排序的回合（Pass） 
# range(1, 5) 會執行 loop = 1, 2, 3, 4，共 4 回合（N 個元素需要 N-1 回合）
 
for loop in range(1, 5):
 
     # 內層迴圈：比較與交換相鄰的兩個元素 
     # range(0, 5 - loop)：每一回合結束後，最大值會被送到最後面，因此比較次數會逐回合減 1 
     # 外圈 loop = 1，內圈 range 0 ~ (5 - 1) => index = 0, 1, 2, 3  比 4 次 a[0] 比 a[1] -> a[1] 比 a[2] -> a[2] 比 a[3] ->  a[3] 比 a[4]    
     # 外圈 loop = 2，內圈 range 0 ~ (5 - 2) => index = 0, 1, 2 比 3 次 a[0] 比 a[1] -> a[1] 比 a[2] -> a[2] 比 a[3]  
     # 外圈 loop = 3，內圈 range 0 ~ (5 - 3) => index = 0, 1    比 2 次 a[0] 比 a[1] -> a[1] 比 a[2] 
     # 外圈 loop = 4，內圈 range 0 ~ (5 - 4) => index = 0       比 1 次 a[0] 比 a[1] 
     for index in range(0, (5-loop)):
         # 如果前一個元素比後一個元素大，代表順序錯誤，需要進行交換（由小到大排序）
         if a[index] > a[index+1] :
             # 使用暫存變數 temp 進行經典的三步驟值交換
             temp = a[index]        # 1. 先將左邊的值備份到 temp
             a[index] = a[index+1]  # 2. 將右邊較小的值覆蓋到左邊
             a[index+1] = temp      # 3. 將備份的值放到右邊
     # 內層迴圈結束，代表該回合（loop）的比較與交換已完成        
     print()
 
     # 印出當前是第幾次（第幾回合）排序的標題，並且不換行
     print(f'第 {loop} 次排列: ' , end = '')
 
     # 使用 for 迴圈印出當前回合排序後的陣列最新狀態
     for j in range(5):
         print(f' a[{j:d}]={a[j]:3d}', end = '  ')

[結果]

排  序  前 :  a[0]=  4   a[1]=-15   a[2]= 20   a[3]= 13   a[4]=-11  
第 1 次排列:  a[0]=-15   a[1]=  4   a[2]= 13   a[3]=-11   a[4]= 20  
第 2 次排列:  a[0]=-15   a[1]=  4   a[2]=-11   a[3]= 13   a[4]= 20  
第 3 次排列:  a[0]=-15   a[1]=-11   a[2]=  4   a[3]= 13   a[4]= 20  
第 4 次排列:  a[0]=-15   a[1]=-11   a[2]=  4   a[3]= 13   a[4]= 20

** 氣泡排序法（Bubble Sort）比較次數對照表**

回合 (`loop`)	`index` 範圍 (`5 - loop`)	實際比較的索引用途 (`index` 與 `index+1`)	比較次數	確定位置的元素
loop = 1	`range(0, 4)`	`a[0]~a[1]`, `a[1]~a[2]`, `a[2]~a[3]`, `a[3]~a[4]`	4 次	確定 `a[4]` (最大值)
loop = 2	`range(0, 3)`	`a[0]~a[1]`, `a[1]~a[2]`, `a[2]~a[3]`	3 次	確定 `a[3]` (次大值)
loop = 3	`range(0, 2)`	`a[0]~a[1]`, `a[1]~a[2]`	2 次	確定 `a[2]`
loop = 4	`range(0, 1)`	`a[0]~a[1]`	1 次	確定 `a[1]` 與 `a[0]`

規律總結：

總回合數： $N - 1$ 次（本例 $N = 5$ ，共需 4 回合）。

每回合比較次數：第 $k$ 回合需比較 $N - k$ 次，隨著排序推進，每輪比較次數會遞減 1 次。

總比較次數： $4 + 3 + 2 + 1 = 10$ 次。

description	—
tags	python
date	2026-07-21

課程名稱： Python 程式語言

探索