深入了解快速排序算法的穩定性

在初次接觸排序算法穩定性這個概念時，我一直認為複雜度為o(n2)的算法是穩定的，複雜度為o(nlogn)的算法是不穩定的。當時是這樣了解的，複雜度為o(n2)的算法不可能再壞，而複雜度為o(nlogn)的算法在極端情況下可能會退化為o(n2)，例如快速排序。但其實這是錯誤的，穩定性的概念遠沒有這麼複雜，它隻表示兩個值相同的元素在排序前後是否有位置變化。如果前後位置變化，則排序算法是穩定的，否則是不穩定的。穩定性的定義符合常理，兩個值相同的元素無需再次交換位置，交換位置是做了一次無用功。

       之前對穩定性這個概念認識很淺，隻停留在知道這個名詞的層次上，直到最近寫代碼遇到一個詭異的現象才讓我對穩定性有了更深刻的認識。我現在需要對大量資料進行排序，資料範圍有限。針對資料量的大小，可以選擇快速排序和基數排序（可參考：）。在此基礎上，每一個資料都還伴随有一個屬性，在排序過程中也要随之移動這個屬性資料。一種可行方案是将資料和屬性構成一個結構體，然後對結構體進行排序。在排序的過程中隻有指針的移動，沒有實際結構體的移動。這種方案涉及間接尋址，對現有代碼改動較大，沒有采用。

       我采用的方案是在原始快速排序和基數排序基礎上做修改，每當出現元素交換時，就将對應的屬性也進行交換。按這種思路實作的快速排序代碼如下：

上述代碼的結構很簡單，就是在快排基礎上增加屬性元素的交換。基數排序代碼如下：

基數排序代碼稍微有點複雜，需要重新開辟一個新的數組存放屬性資料，但是思想還是在交換原始元素的同時交換屬性元素。雖然思想很簡單，但是還是對自己的實作心存疑慮，同時寫了一個驗證函數，驗證最後的結果是否一緻（最初的想法是如果正确實作則原始元素是排好序的，同時兩種排序算法的屬性元素也應該一緻）：

完成上面的代碼，就可以開始測試。首先測試數組長度小于100時，沒有問題，很沾沾自喜。然後測試1000，第一次沒問題，重複測試就報錯了。很奇怪，多次測試時有正确有錯誤，一時搞不清楚到底怎麼回事。開始認為應該代碼有bug，但是仔細debug了一天也沒有搞明白到底哪個地方出錯了。後來，換了一個思路：快排和基數排序都屬于比較進階的排序，我找個最笨的排序先保證正确性，然後去和快排、基數排序比較。之後按照這個思路把冒泡排序的算法實作了：

對于快排和基數排序，我開始認為是基數排序的算法實作錯了，畢竟這個算法是首次使用。但是結果令我吃驚：冒泡排序的結果和基數排序的結果完全一緻，反倒是快速排序和冒泡排序的結果不一緻！太出乎意料了，問題找了半天沒想到是出在自己擅長的快排上面。快排怎麼可能會出錯呢，畢竟用了這麼久。很長時間内我也沒有找到問題所在。後來我将equals方法修改了下，去掉return，把所有不比對的資料都列印出來，一列印終于發現問題所在！

列印結果顯示，錯誤總是出在兩個值相同的元素間，一瞬間就明白怎麼回事了：快速排序是不穩定排序，它可能會交換兩個值相同的元素，是以這根本就不是一個bug。沒想到debug兩天原來是做的無用功。

為了能汲取教訓，我又仔細分析了一下為什麼快排是不穩定排序。出現不穩定的關鍵是兩個do-while循環：

兩個循環在進行元素比較時，分别用了小于和大于操作（也可以改用小于等于和大于等于，但是對性能沒有影響）。這就意味着如果出現和pivot值相同的元素，它都會被作為交換對象而移動到pivot的前面或者後面，這就出現了值相同的元素會交換順序的問題，因而是不穩定的。