一、什麼是排序的穩定性
穩定性定義: 對於待排序序列中，若存在兩個相等的元素 A 和 B，並且 A 在 B 之前，那麼排序後 A 仍然排在 B 前面 ——則該排序算法是 穩定的。
反之，如果可能出現相等元素的相對位置改變，就叫“不穩定排序”。
二、如何判斷穩定性(通用方法)
判斷思路非常簡單:
“當兩個相等的元素在排序過程中有可能交換（或跨過彼此）時，它就是不穩定的。”
換句話説:
- 只要算法會跨區間交換非相鄰元素，就可能破壞穩定性。
- 如果算法只比較並交換相鄰元素（並保持相等時不交換），通常是穩定的。
三、各算法穩定性分
|
算法
|
穩定性
|
原因分析
|
|
冒泡排序
|
穩定
|
只交換相鄰元素，> 才交換，== 不動
|
|
插入排序
|
穩定
|
插入時從後往前比較，<= 時不交換
|
|
選擇排序
|
不穩定
|
可能跨區交換，如 [5a, 3, 5b] → [3, 5b, 5a]
|
|
希爾排序
|
不穩定
|
跨 gap 交換，可能跳過相等元素
|
|
快速排序
|
不穩定
|
pivot 交換時可能讓相等元素越過
|
|
歸併排序
|
穩定
|
合併時若相等，優先取左邊元素
|
|
堆排序
|
不穩定
|
堆調整會跨層交換，打亂相等順序
|
|
桶排序
|
穩定
|
按順序分配或統計，不改變相對順序
|
✅ 一句話總結：
判斷排序算法是否穩定：
看它在相等元素時是否可能“跨越”或“交換”順序。
- 相鄰交換 + 不動相等項 → 穩定
- 跨區交換或重建結構 → 不穩定
本文章為轉載內容，我們尊重原作者對文章享有的著作權。如有內容錯誤或侵權問題，歡迎原作者聯繫我們進行內容更正或刪除文章。