排序的“公平性”：穩定性是什麼？以插入排序爲例¶

想象這樣一個場景：你和同桌一起參加跑步比賽，你們倆同時衝過終點線，成績完全相同。教練說按“先到先排”的規則頒獎，那麼你們倆的獎項順序應該和賽前的起跑順序一致——你先跑就排在你前面，同桌後跑就排在他後面。這就像排隊時遇到“長得一樣”的人，大家默認按先來後到的順序，這就是一種“公平”。

在計算機的排序算法裏，也有這種“公平性”，它的名字叫做穩定性。

什麼是排序的“穩定性”？¶

簡單說，穩定性就是指：當排序後的數組中出現兩個值相等的元素時，它們在排序前的相對順序是否保持不變。如果保持不變，這個排序算法就是穩定排序；如果順序變了，就是不穩定排序。

舉個例子：假設我們有一個數組 [3, 1, 3, 2]，這裏有兩個相等的元素 3（第一個 3 在原數組的第 0 位，第二個 3 在原數組的第 2 位）。如果排序後，這兩個 3 的位置依然是“第一個 3 在前面，第二個 3 在後面”，那就說明這個排序算法是穩定的。

插入排序如何體現“穩定性”？¶

我們用插入排序來具體看看它是如何保持穩定性的。插入排序的核心思想是：每次從無序部分取出一個元素，插入到有序部分的正確位置。

模擬插入排序過程¶

以數組 [3, 1, 3, 2] 爲例，它包含兩個相等的 3，我們來一步步模擬插入排序：

初始狀態：有序部分爲空，無序部分爲 [3, 1, 3, 2]。
處理第一個元素 3：有序部分變爲 [3]，無序部分變爲 [1, 3, 2]。
處理第二個元素 1：1 比 3 小，插入到 3 前面，有序部分變爲 [1, 3]，無序部分變爲 [3, 2]。
處理第三個元素 3：現在有序部分是 [1, 3]，當前元素是 3。我們需要找到 3 在有序部分的位置：
- 比較 3 和有序部分的最後一個元素 3，發現它們相等。此時插入排序的“關鍵”來了：相等時不交換，直接把新元素插入到相等元素的後面。
- 所以 3 插入到有序部分的末尾，有序部分變爲 [1, 3, 3]，無序部分變爲 [2]。
處理第四個元素 2：2 比 3 小，插入到 3 前面，再比 1 大，最終有序部分變爲 [1, 2, 3, 3]。

最終排序結果是 [1, 2, 3, 3]，原來兩個 3 的相對位置（第一個 3 在原數組第 0 位，第二個 3 在原數組第 2 位）在排序後依然保持：第一個 3 出現在第二個 3 前面。

爲什麼插入排序是穩定的？¶

插入排序的“穩定性”來源於它的插入邏輯：當插入一個新元素時，它會從有序部分的末尾開始，逐個與元素比較，遇到相等的元素就停止移動，直接把新元素插在後面。這就保證了：如果兩個元素相等，後出現的元素永遠不會跑到先出現的元素前面。

比如我們再用一個例子 [2, 2, 1] 測試：
- 初始有序部分 [2]，處理第二個 2 時，比較發現 2 等於有序部分的最後一個元素 2，所以直接插在後面，有序部分變爲 [2, 2]。
- 接着處理 1，插入到有序部分最前面，最終結果 [1, 2, 2]。原來兩個 2 的相對順序（先出現的 2 在前面，後出現的 2 在後面）完全保持。

穩定性的意義¶

爲什麼要關心穩定性？想象你在做成績排名：先按分數排序，分數相同的同學按學號從小到大排列。如果排序不穩定，兩個分數相同的同學學號順序可能被打亂，導致原本學號小的同學拿到了錯誤的排名。這時候，穩定性就保證了“公平性”——相同條件下，原始順序被尊重。

插入排序正是因爲這種“公平性”，在處理重複元素時表現優異。比如電商訂單按“金額+時間”排序，相同金額的訂單按下單時間先後處理，穩定性就確保了最早下單的客戶優先。

總結¶

排序的“公平性”就是穩定性：當兩個元素的值相等時，它們在排序前後的相對順序是否不變。插入排序通過“相等時不交換，直接後插”的插入邏輯，天然保證了穩定性。這就像排隊時遇到“同分選手”，嚴格按原始順序排列，讓每個元素都“公平”對待。

下次當你看到排序算法時，不妨想想：如果有兩個相同的數字，它們的“座位”會被打亂嗎？如果沒有，那它大概率就是穩定的。而插入排序，就是一個永遠“公平”的排序選手。