排序算法番外篇 算法的穩定性

定義：

假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，d=r，且排序前d在r之前，而在排序後的序列中，d仍在r之前，則稱這種排序算法是穩定的；否則稱為不穩定的。

通常情況：

堆排序、快速排序、希爾排序、直接選擇排序不是穩定的排序算法，而基數排序、冒泡排序、直接插入排序、折半插入排序、歸并排序是穩定的排序算法。

但是，對于不穩定的排序算法，隻要舉出一個執行個體，即可說明它的不穩定性；而對于穩定的排序算法，必須對算法進行分析進而得到穩定的特性。需要注意的是，排序算法是否為穩定的是由具體算法決定的，不穩定的算法在某種條件下可以變為穩定的算法，而穩定的算法在某種條件下也可以變為不穩定的算法。

有空會在下面補充一些算法不同的寫法，穩定性則會改變。