排序算法基礎：定義、穩定性、分類與性能指標全解析

排序的形式化定義

設含 n 筆記錄的序列為 {r₁,r₂,...,rₙ}，對應關鍵字 {k₁,k₂,...,kₙ}。排序即確定排列 p₁,p₂,...,pₙ，使關鍵字滿足非遞減（或非遞增）關係：kₚ₁ ≤ kₚ₂ ≤ ... ≤ kₚₙ，得到有序序列 {rₚ₁,rₚ₂,...,rₚₙ}。

穩定性：核心屬性

穩定排序：若 kᵢ = kⱼ (i≠j) 且排序前 rᵢ 在 rⱼ 前，排序後 rᵢ 仍在 rⱼ 前。
不穩定排序：可能打破相對順序。
通俗例：小明小芳總分相同，排序前小明在前，穩定排序後小明仍在前。

內排序 vs 外排序

內排序三大性能指標

1. 時間性能：比較次數 + 移動次數 → 越少越好
2. 輔助空間：除數據本身外的額外存儲 → O(1) 為就地排序
3. 算法複雜度：代碼實現難度 → 影響維護與優化

四大類八種經典內排序算法

1. 交換排序

• 冒泡排序
• 快速排序

2. 插入排序

• 直接插入排序
• 折半插入排序
• 希爾排序

3. 選擇排序

• 簡單選擇排序
• 堆排序

4. 歸並排序

• 二路歸並排序

後續章節將逐一深入講解各算法原理、代碼實現與優化策略。