排序的‘公平性’：穩定性是什麼？以插入排序爲例

排序的“穩定性”指排序後相等元素的相對順序是否保持不變，保持則爲穩定排序。插入排序通過獨特的插入邏輯實現穩定性。 插入排序核心是將無序元素逐個插入有序部分。當插入相等元素時，不交換，直接插在相等元素之後。例如數組[3,1,3,2]，處理第二個3時，因與有序部分末尾的3相等，直接插入其後方，最終排序結果[1,2,3,3]，原兩個3的相對順序未變。 穩定性的關鍵在於保留相等元素的原始順序。這在實際場景中至關重要，如成績排名、訂單處理等需按原始順序公平排序的情況。插入排序因“相等不交換，後插”的邏輯，天然保證了穩定性，讓重複元素始終按原始順序排列，體現“公平性”。