對于排序算法，相信你一定不陌生吧！如我們常見的幾大經典排序：
「冒泡排序」、「插入排序」、「選擇排序」、「快速排序」、「歸并排序」、「堆排序」等等。
這些排序算法中，性能、記憶體消耗各有優劣，同時也各有各的适用場景，而我們也不能僅僅從時間複雜度和空間複雜度的優劣去評斷一個排序算法的好與壞，比如「冒泡排序」和「插入排序」，兩者的時間複雜度均是O(n²)，空間複雜度也都是O(1)，但是插入排序卻更常用，而且在很多實際場景中，執行效率更高，至于原因，你可以思考一下，此文暫不做讨論。
而排序算法中，除了時間複雜度和空間複雜度，還有着一個我們比較常關注的性質：「穩定性」。
我們這裡簡單描述一下什麼是排序算法的穩定性：
❝
對于某一種排序算法，如果待排序的序列中存在值相等的元素，經過排序之後，相等元素之間原有的先後順序保持不變，那麼就說這個排序算法是穩定的。
❞
而上面所提到的幾種排序算法中，冒泡排序、插入排序、歸并排序屬于穩定排序，選擇排序、快速排序、堆排序屬于不穩定排序。
簡單舉個例子：
假設對數組[
3, 2, 2, 5, 1, 4
]進行遞增排序，數組中有兩個元素是相等的即
2
，為友善辨別，我們先用
2'
表示第二個
2
，即原數組為：[
3, 2, 2', 5, 1, 4
]。
- 如果使用穩定排序，那麼排序後有且僅有一種結果：[
1, 2, 2', 3, 4, 5
- 如果使用不穩定排序，那麼排序後，可能會出現這種結果：[
1, 2', 2, 3, 4, 5
排序的穩定性很好去了解，也很容易去分析。但是你有沒有想過：
❝
「既然所有的排序算法排出來的結果都是有序的，為什麼還要區分穩定性和不穩定性的算法呢？」
❞
我們用下面一個場景來說明。
假設有一萬條訂單記錄，要對這些訂單進行一個排序，要求按照金額由小到大的順序排列，如果訂單金額相同，則按照下單時間的先後進行排列。
假設訂單資料為：
在開始進行排序時，有一點先要弄明白：像這種存在需要對多個關鍵字進行排序的，每一次排序隻能基于其中某一個且僅一個關鍵字進行排序，無法對多個關鍵字同時排序。之是以提這一點，是為了避免有人拿Java的比較器Comparator做對比，那根本是兩碼事。
而對于需要針對多個關鍵字排序的情況，優先級最高的要放在最後排才行，比如這裡先按照金額大小排序，在金額大小相同的情況下，再按照下單時間排序，優先級最高的就是金額，那麼就應該最後再排金額。如果先排金額，在排序後，如果有金額相同的，再排下單時間，那麼最後的結果就是以下單時間的先後為準了，你好好想一想，是不是這麼回事？
好，那我們進行排序，先對下單時間進行排序，得到的結果為：
得到這個結果後，我們再對金額進行一次排序就OK了，但是這裡為了達到需求要求的效果，「即金額相同的，下單時間早的要排在前面」，則第二次排序隻能用穩定排序。如果使用不穩定排序，第二次按照金額排序後，得到的結果雖然在金額上是有序的，但下單時間上就不一定有序了，換一種說法就是：第一次按照訂單時間排序的結果，沒有被第二次按照金額排序利用上，先看圖：
使用穩定排序後的結果：
這樣子你應該明白了吧，如果使用不穩定排序，那麼第二次排序後的結果，就可能不符合要求，「不穩定排序會改變相同元素的原有順序」。在這個場景中，不穩定排序就可能會把金額均是30的原有順序改變了(注意哦，這個順序是已經按照下單時間排好序的結果)，進而導緻最終的排序結果對于金額相同的，沒有按照時間先後來排序。但是這種問題，使用穩定排序就不會出現。
是以，現在你明白了吧，之是以區分排序的穩定性和不穩定性，是有它的實際應用場景的，它的意義在于：
❝
在需要對多個(也意味着多次)具有優先級的關鍵字進行排序的場景下，穩定排序能利用上一次排序的結果服務于本次排序，進而保證對于值相同的元素的兩次排序結果相同。
❞
用這個場景來解釋就是：
第一次排序先對下單時間進行排序，得到的排序結果中，兩個金額為30的記錄在下單時間上已經是有序的了；然後第二次排序對金額進行排序，由于使用了穩定排序，兩個金額為30的記錄的順序就不會被改變了，這就相當于第一次排序的結果被第二次排序利用上了。
如果你還是不能夠完全了解，再舉一個實際場景：
對考生的成績進行排名，如果總分相同的，則按照國文分數高低排，如果國文分數還相同的，繼續按照數學分數高低排。
看到這個例子，你是否恍然大悟了呢？
在這個例子中，排序的優先級是：總分 > 國文 > 數學，如果使用穩定排序，我們就能得到預期且是正确的結果；如果使用不穩定排序，就有可能會出現，對于總分相同的，國文分數較低的就排在了更前面，這個結果對于成績排名，就不是正确的。
這就是穩定排序的實際應用場景，對于某些場景，不穩定排序得到結果可能是不正确的。
「THE END」
【你的關注和支援，是我創作的最大動力】