排序演算法怎麼選？穩定性、時間複雜度與記憶體取捨

排序演算法的目標都是把資料依鍵值排列，但「速度最快」沒有脫離情境的單一答案。資料量、原本是否接近有序、能否使用額外記憶體、是否要求相同鍵值維持原順序，都會改變選擇。冒泡、插入、選擇、合併、快速與堆積排序的差別，正是比較次數、移動成本、最壞情況與空間需求之間的取捨。

時間複雜度描述成長趨勢

演算法分析常用大 O 記號描述輸入規模 n 增加時，工作量如何成長。O(n²) 表示資料量加倍，主要工作量可能接近四倍；O(n log n) 的成長較慢，通常更適合大型資料。

大 O 不等於實際秒數。常數成本、程式語言、快取、資料分布與硬體都會影響結果。當 n 很小時，步驟簡單的 O(n²) 演算法可能比結構複雜的 O(n log n) 更快。它提供的是規模趨勢，不是每次執行的精準計時。

若兩筆資料的排序鍵相同，穩定排序會維持它們原本的先後。例如員工名單先依姓名排序，再以部門做穩定排序，同部門內仍可保留姓名順序。若第二次排序不穩定，相同部門的排列可能被打亂。

穩定性不是「結果不會出錯」，也不是執行時不會當機。只排序互不相同的數字時，甚至看不出穩定與否；但處理具有多欄位的紀錄時，它可能是功能需求。

冒泡排序反覆比較相鄰元素，若順序錯誤就交換。每一輪會把較大元素逐步推到尾端。實作直觀，若記錄某輪沒有交換，還能提早結束；接近有序資料時可能表現不差。

一般與最壞情況需要 O(n²) 比較，因此不適合大型資料。只交換嚴格逆序的相鄰元素時，它可以保持穩定。視覺化工具常用它展示排序，是因為每一步容易理解，不代表正式系統應優先採用。

插入排序把左側視為已排序區，每次取下一個元素，向左尋找位置並把較大元素移開。當資料本來接近有序時，移動距離短，速度可接近 O(n)；完全反向時則退化為 O(n²)。

它額外空間少、可穩定實作，對小陣列很實用。許多成熟排序方法會在分割後的子陣列很小時，改用插入排序降低函式呼叫與管理成本。

選擇排序每輪從未排序區找最小值，放到前方正確位置。無論資料原本多整齊，仍要掃描剩餘區域，所以比較次數維持 O(n²)。

它的優點是交換次數相對少。如果寫入或交換成本遠高於比較，這個特性可能有價值。傳統直接交換最小值的版本通常不穩定，因為遠距交換可能跨過相同鍵值元素。

合併排序把資料分成兩半，分別排序，再用兩個游標把兩個有序序列合併。每一層總共處理約 n 個元素，分割深度約為 log n，因此最壞時間仍是 O(n log n)。

陣列版本通常需要 O(n) 額外空間保存合併結果，但容易保持穩定，執行時間也較可預測。對鏈結串列或外部儲存資料，合併操作尤其自然。代價是額外記憶體與資料搬移。

快速排序選一個樞紐，把較小與較大元素分到兩側，再遞迴處理。分割平衡時，平均時間為 O(n log n)，而且常具有良好快取區域性。

若樞紐反覆選到極端值，分割會嚴重不平衡，最壞時間退化為 O(n²)。隨機選樞紐、三數取中與混合策略可降低風險。常見原地版本通常不穩定，但不同實作可有不同空間與穩定性。

堆積排序先把陣列整理成最大堆，讓根節點是最大值，再把它交換到尾端並修復堆。建堆後，每次取出極值需 O(log n)，整體最壞時間為 O(n log n)，且可用很少額外空間。

它通常不穩定，存取位置跳動也可能讓快取表現不如快速排序，但在重視最壞時間與空間上限時很有價值。

排序視覺化會故意在比較或交換之間加入延遲，讓人看清步驟。畫面更新、動畫與顏色繪製的成本，可能遠高於演算法本身。柱狀圖跑得比較快，只能幫助理解路徑，不能取代在相同資料、相同環境下的基準測試。

比較時還要控制輸入。隨機、已排序、反向、有大量重複值的資料，會暴露不同優缺點。只測一次小陣列，很容易得到偶然結論。

先確認是否需要穩定性，再看資料規模與記憶體限制。小型或接近有序資料可考慮插入排序；要求穩定且能提供額外空間時，合併排序常是清楚選項；重視平均實務速度可採成熟的快速排序變體；需要最壞 O(n log n) 且空間受限時，可考慮堆積排序。

實務上通常應使用語言標準函式庫，因為它可能採混合演算法並處理各種邊界。學習六種排序的目的，不是每次都重新手寫，而是看懂穩定性、複雜度和記憶體如何共同決定工具背後的設計。