Python 排序算法的穩定性及其彙總
一、先明確：穩定性的核心意義
1. 穩定排序的價值
- 同一班級的學生，在按成績排序後，仍保持原班級內的相對順序（如同一班級中成績相同的學生，原始排名不變）；
- 無需額外記錄關聯信息，直接通過多輪穩定排序即可實現複雜需求。
2. 穩定性的直觀示例
- 穩定排序後（相等元素 2 的索引 0 < 2 保持不變）：
[(1, 1), (2, 0), (2, 2), (3, 3)] - 不穩定排序後（相等元素 2 的順序被打亂）：
[(1, 1), (2, 2), (2, 0), (3, 3)]
二、Python 常用排序算法穩定性彙總表
|
排序算法
|
穩定性
|
時間複雜度（平均）
|
時間複雜度（最壞）
|
空間複雜度
|
核心原理
|
Python 內置支持
|
|
冒泡排序
|
穩定
|
O(n²)
|
O(n²)
|
O(1)
|
相鄰元素兩兩比較，逆序則交換
|
無（需手動實現）
|
|
插入排序
|
穩定
|
O(n²)
|
O(n²)
|
O(1)
|
逐個插入到已排序序列的正確位置
|
無（需手動實現）
|
|
歸併排序
|
穩定
|
O(n log n)
|
O(n log n)
|
O(n)
|
分治思想，合併兩個有序子序列
|
無（需手動實現）
|
|
基數排序
|
穩定
|
O (d・n)（d 為位數）
|
O(d·n)
|
O (n + k)（k 為基數）
|
按位分組排序（從低到高 / 高到低）
|
無（需手動實現）
|
|
選擇排序
|
不穩定
|
O(n²)
|
O(n²)
|
O(1)
|
每次選最小元素放到已排序區末尾
|
無（需手動實現）
|
|
快速排序
|
不穩定
|
O(n log n)
|
O (n²)（最壞）
|
O (log n)（遞歸棧）
|
分治思想，以基準元素分區
|
無（需手動實現）
|
|
堆排序
|
不穩定
|
O(n log n)
|
O(n log n)
|
O(1)
|
構建大頂堆 / 小頂堆，依次提取堆頂
|
無（需手動實現）
|
|
Timsort（Python 內置）
|
穩定
|
O(n log n)
|
O(n log n)
|
O(n)
|
歸併排序 + 插入排序（混合優化）
|
|
關鍵結論：
三、核心排序算法實現與穩定性驗證
1. 穩定排序算法（實現 + 驗證）
（1）冒泡排序（穩定）
穩定性保證：僅當元素嚴格逆序時才交換，相等元素不交換，保留原始順序。
python
運行
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
swapped = False
# 每輪遍歷後，末尾 i 個元素已排序，無需再比較
for j in range(n - 1 - i):
# 僅當 arr[j] > arr[j+1] 時交換（相等不交換）
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped: # 無交換説明已有序，提前退出
break
return arr
# 穩定性驗證（元素為元組，第一列為排序鍵，第二列為原始索引）
test_arr = [(2, 0), (1, 1), (2, 2), (3, 3)]
sorted_arr = bubble_sort(test_arr.copy())
print("冒泡排序結果（穩定）：", sorted_arr)
# 輸出：[(1, 1), (2, 0), (2, 2), (3, 3)]（相等元素 2 的索引順序不變）（2）歸併排序（穩定）
穩定性保證：合併時，若兩個子數組的元素相等，優先取左子數組的元素，保留原始順序。
python
運行
def merge_sort(arr):
if len(arr) <= 1:
return arr
# 分治：拆分為左右兩個子數組
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# 合併兩個有序子數組
return merge(left, right)
def merge(left, right):
res = []
i = j = 0
while i < len(left) and j < len(right):
# 相等時優先取左子數組元素（保證穩定性）
if left[i] <= right[j]:
res.append(left[i])
i += 1
else:
res.append(right[j])
j += 1
# 拼接剩餘元素
res.extend(left[i:])
res.extend(right[j:])
return res
# 穩定性驗證
test_arr = [(2, 0), (1, 1), (2, 2), (3, 3)]
sorted_arr = merge_sort(test_arr)
print("歸併排序結果（穩定）：", sorted_arr)
# 輸出：[(1, 1), (2, 0), (2, 2), (3, 3)]（3）Timsort（Python 內置，穩定）
- 對小規模子數組（默認長度 ≤ 64）使用插入排序（高效且穩定）；
- 對大規模子數組使用歸併排序（穩定且適合大數據量）；
- 自動識別數組中的 “有序段”（run），減少排序次數。
python
運行
# Timsort 穩定性驗證
test_arr = [(2, 0), (1, 1), (2, 2), (3, 3)]
sorted_arr = sorted(test_arr) # 或 test_arr.sort()
print("Timsort 結果（穩定）：", sorted_arr)
# 輸出：[(1, 1), (2, 0), (2, 2), (3, 3)]2. 不穩定排序算法（實現 + 穩定性破壞示例）
（1）選擇排序（不穩定）
穩定性破壞：交換過程可能導致相等元素的相對順序改變。
python
運行
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
# 找到無序區最小元素的索引
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# 交換最小元素與無序區第一個元素（可能破壞穩定性）
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# 穩定性破壞示例
test_arr = [(2, 0), (1, 1), (2, 2), (3, 3)]
sorted_arr = selection_sort(test_arr.copy())
print("選擇排序結果（不穩定）：", sorted_arr)
# 輸出：[(1, 1), (2, 2), (2, 0), (3, 3)]（相等元素 2 的索引順序被打亂）（2）快速排序（不穩定）
穩定性破壞：基準元素與其他元素交換時，可能導致相等元素的相對順序改變。
python
運行
def quick_sort(arr):
if len(arr) <= 1:
return arr
# 選擇基準元素（此處選第一個元素，可優化為隨機選擇）
pivot = arr[0]
# 分區：小於基準、等於基準、大於基準
left = [x for x in arr[1:] if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr[1:] if x > pivot]
# 遞歸排序併合並（middle 保留相等元素順序，但分區交換可能破壞整體穩定）
return quick_sort(left) + middle + quick_sort(right)
# 穩定性破壞示例（複雜場景下更明顯）
test_arr = [(3, 0), (2, 1), (3, 2), (1, 3)]
sorted_arr = quick_sort(test_arr)
print("快速排序結果（不穩定）：", sorted_arr)
# 可能輸出：[(1, 3), (2, 1), (3, 2), (3, 0)]（相等元素 3 的順序被打亂）四、穩定性的實際應用場景
1. 多關鍵字排序
python
運行
# 原始數據：(日期, 金額, 原始索引)
data = [(20250101, 100, 0), (20250102, 200, 1), (20250101, 150, 2), (20250102, 200, 3)]
# 第一步：按金額降序排序（穩定排序）
sorted_by_amount = sorted(data, key=lambda x: -x[1], reverse=False)
# 第二步：按日期升序排序（穩定排序，保留金額排序結果）
final_sorted = sorted(sorted_by_amount, key=lambda x: x[0])
print("多關鍵字排序結果：", final_sorted)
# 輸出：[(20250101, 150, 2), (20250101, 100, 0), (20250102, 200, 1), (20250102, 200, 3)]
# 説明：同一日期內，金額降序；金額相同時，原始索引順序不變2. 保留原始關聯信息
python
運行
# 學生數據：(成績, 學號)
students = [(85, "001"), (92, "002"), (85, "003"), (78, "004")]
# 使用穩定排序（sorted()）
sorted_students = sorted(students, key=lambda x: -x[0])
print("成績排序（保留學號順序）：", sorted_students)
# 輸出：[(92, "002"), (85, "001"), (85, "003"), (78, "004")]
# 説明：成績相同的 001 和 003，原始順序不變3. 避免數據關聯丟失
五、關鍵注意事項
1. 如何判斷排序算法是否穩定？
- 核心原則：相等元素是否會被交換位置；
- 快速判斷技巧：
- 基於 “交換” 的排序（冒泡、插入）：穩定（僅逆序交換）；
- 基於 “選擇” 的排序（選擇、快排、堆排）：不穩定（直接交換最小 / 最大元素）；
- 基於 “合併” 的排序（歸併、Timsort）：穩定（合併時保留順序）。
2. Python 中排序的 key 函數與穩定性
python
運行
# key 函數不影響穩定性
data = [(2, 0), (1, 1), (2, 2)]
sorted_data = sorted(data, key=lambda x: x[0]) # key 為第一個元素
print(sorted_data) # 輸出：[(1, 1), (2, 0), (2, 2)]（相等 key 保留原始順序）3. 何時可以忽略穩定性？
- 排序的元素是 “獨立個體”（無關聯信息需要保留）；
- 排序鍵是唯一的（無相等元素，穩定性無意義）；
- 對排序效率要求極高，且空間敏感（可選擇堆排等不穩定算法）。
六、總結
- 多關鍵字排序、保留關聯信息 → 穩定排序（歸併、Timsort、冒泡 / 插入（小規模））；
- 空間敏感、無關聯信息 → 不穩定排序（堆排、快排）；