關于排序算法中的穩定與不穩定的說法

最近在複習資料結構，這裡記錄一些基礎知識和複習感悟，以飨路人，互幫互助、共同富裕。

排序算法的穩定性判斷（既穩定的還是不穩定的）

大白解釋：對于一個序列｛5，6，4，4，1，2，3｝的七個數字，你會發現第三個和第四個都是'4'，沒錯，這裡為友善叙述，計為4（1）和4（2），且記住4（1）領先于4（2），就是說4（1）排在4（2）前面；如果按從小到大排序，得到的結果是｛1，2，3，4，4，5，6｝，如果，排好的序列中的這裡的第四個和第五個'4'，分别對應上個序列的4（1）和4（2）則說明此排序算法是穩定的，即沒有改變相同數字最初的順序；若是這兩個對應的是4（2）和4（1），則改變了相同數字最初的次序，稱為次算法是不穩定的。

小智解釋：有給定的多條記錄的一個序列R＝｛r1，r2，…，rn｝，其對應的關鍵字為K＝｛k1，k2，…，kn｝，則可以描述為：

輸入：序列R＝｛r1，r2，…，rn｝，關鍵字K＝｛k1，k2，…，kn｝

輸出：新序列R'＝｛r1'，r2'，…，rn'｝，關鍵字K＝｛k1'，k2'，…，kn'｝，使得k1'<=k2'<=…<=kn'

如果記錄的關鍵字都沒有重複出現，那麼排序算法可以得到唯一的結果；否則，排序的結果可能不唯一。當關鍵字可以重複出現時，假設ki＝kj，且在排序前的序列R中，Ri領先于Rj，若在排序後的序列R'中Ri仍領先于Rj，則稱排序算法是穩定的；否則，若排序後的序列R'中，Rj領先于Ri，則稱排序算法是不穩定的。例如，序列｛5，6，4（1），4（2），1，2，3｝，用小括号中數字區分數字'4'。若排序後得到｛1，2，3，4（2），4（1），5，6｝，則該排序方法是不穩定的。