排序演算法中的「穩定」和「不穩定」，有沒有一個結論性的因素導致該演算法穩定或不穩定？

01-08

對於「冒泡」、「插入」、「歸併」這些穩定排序演算法，和「選擇」、「快排」、「希爾」這些不穩定排序演算法，到底是什麼因素導致了某個演算法是穩定/不穩定的？還是說並沒有一個結論性的內因，只能通過結果判斷該演算法是否穩定？

拜託，排序的穩定性指的是是否具備原序列中相等的元素排序後相對位置不變的性質，而不是性能是否穩定。。。

答案，需要對每個演算法單獨考察穩定性，自己去找本數據結構教材看上面的證明。

@winter大大理解錯了，排序的穩定性並不是演算法性能是否穩定。演算法性能的穩定性，一般是說是否會退化。

需要分析演算法本身的策略，是否能夠具有穩定性。也就是保證鍵值相同的元素排序前後相對次序不變。

具體問題具體分析。例如，插入排序，前面的元素先插入已排序的序列，後插入的元素依次前移，直到不比前面的位置的大。相同的元素是不會越過的。

嚴格證明可以使用數學歸納法，對長度歸納。例如歸併排序，長度為1時顯然是穩定的，如果你小於n都穩定，很容易推出n+1也穩定。

不穩定性就找反例了。

選擇排序用最小值和未排序元素做交換，可能會破壞相同鍵值元素的次序。

而快速排序，樞紐元如果是重複的值，選擇不同位置的相同元素，就可能破壞次序。

注意: 大小比較和交換必須寫正確，常見的錯誤就是序關係定義成了小於等於。雖然有時不影響正確性，但會影響穩定性。

http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

結論性的因素似乎沒有，還是需要單獨證明。

要很牽強地說那種感覺，使得每次操作之後相同key值元素相對位置保持不變，大概就是「熵」在每次排序處理之後的改變較小的時候，或者說原先的元素比較「懶惰」的時候，容易出現這種情況。

比如selection sort，每次交換的元素跑遠不說，被交換元素也很無辜，只是恰好在那裡而已；而insertion sort，插進來的傢伙是順序選擇的，其他人只是拱一拱身子；shell sort也是和很遠的傢伙進行交換，忽略了一定的局部特性；partition過程之慘烈更不必多說；merge則只需要大家一點點按原來順序站好隊慢慢擠到一起罷了。

排序本來雖然是共通點不容易總結的演算法，但可能真存在更高階的判斷方法吧。

題外話，當然所有的unstable排序都可以變成stable的，只要在key附加上原先的次序就好了。

單論排序的話, 我認為不同的swap策略決定了它們是否穩定.

大概理解了題主的意思，說一下我的看法。

內因就是：對於一個沒有被排好序的元素，它在其他元素進行排序（也就是這個操作不會導致它本身到達所應該到的位置）的過程中，會不會相對於它所應該在的位置（即排序後的正確位置）發生改變，即有可能本來是在正確位置左側，被換到了右側去。

這是對於in-place的排序的理解。

merge sort由於不是in-place的，貌似沒法這樣解釋。

又想了一下，其實可以這樣可慮：

排序演算法的目的就是：讓每個元素到達它所應該在的正確的位置。同樣的，也可以是：讓每個位置容納正確的元素。

以元素為對象進行考慮，貌似應該是stable的，比如插入和冒泡，以位置為對象進行考慮的，貌似是unstable的，比如選擇和快排。

（對，以上都是我猜的，我也沒在哪裡看到過這樣的理論，我也不知道對不對。。

導致不穩定演算法實現的常見情形是：

存在交換操作，並且交換區間兩端點的元素之一可能等於區間內的某個元素，並且後續演算法實現無針對上述不穩定交換而進行的矯正操作。

易證。。。

當只考慮演算法的穩定性時，往往是指演算法本身，即演算法的最簡單實現的穩定性：

選擇，堆排，快排，shell等都是上述情形，所以是不穩定的

歸併，插入，冒泡等都不是上述情形，並且是穩定的

但事實上，任意演算法都有同階複雜度的穩定和不穩定實現。如加入預處理操作，將元素次序也嵌入key，那麼一定是穩定的；或者，加入後處理操作，將相等的元素按原次序重新排序(矯正操作)，那麼也一定是穩定的

以上也純屬自己猜想，無引用，不知這樣理解行不行，反正自己這樣記憶從沒出現過問題。。。

一般出現分治且伴隨元素交換操作的都是不穩定的。

我認為任何（基於比較的）排序都可以實現成穩定的或不穩定的。

在比較的時候隱式地將交換前的下標作為最次要關鍵字，則就是穩定的。

在比較兩元素相等的時候隨機交換或不交換就可以不穩定。

一般情況下，交換排序類型里，是以是否是相鄰交換來判斷是否穩定的，而不是演算法的性能上，演算法的性能在實際運行中確實是有可能出現效率下降的情況。但是這個和交換的穩定性沒有關係

從演算法應用角度談談自己看法，例如我們某項目應用場景的數據結構比較複雜，有數據量較小的數據集合，也有大的資料庫或大數據，這時可能在小數據和大數據的排序演算法上都用的冒泡排序，那麼在數據量較小時冒泡感覺較快，數據量大時冒泡就較慢，而快速排序演算法可能正好相反，大數據量是快速排序確實快，小數據量時這種類似二分法理念的演算法反而慢了。

這時候對開發人員來說，就會產生主觀臆斷，認為某某演算法慢，或者不穩定。

解決辦法就是在不同數據需要排序的應用場景用最優的排序演算法，靈活配置，這樣會快，顯得穩定。

真正意義上的不穩定，可能是演算法寫錯了，或者寫了個爛演算法。

舉個例子，打遊戲時用fpe檢索內存修改數據，同一款遊戲修改時， 32m內存的pc和64m的pc修改延遲時間就有差異，在win98時代很明顯。

我覺得當出現間隔多個元素之間互相比較並根據比較結果交換位置的時候，就可能改變相同值的相對順序，這樣就會導致不穩定。比如選擇，希爾

目前看來，只能是具體排序演算法具體分析了，沒有一個統一的結論。

插入和冒泡的交換隻在相鄰的元素間進行

歸併排序也容易證明穩定性

其它三種會跳著交換元素，所以不穩定

我認為不會有一個統一的方法，否則會什麼這麼多人糾結基數排序的穩定性問題呢

交換，特別是跨元素、伴隨著有不穩定位置的交換的時候，就可能導致演算法不穩定

應該沒什麼結論性因素吧，自己腦子裡過一遍演算法的流程(包含相同鍵值的輸入)就知道是否穩定了。