[数据结构与算法]排序算法稳定性

排序算法稳定性

排序算法稳定性：假设待排序序列中有两个元素相等，而且在排序前和排序后两个相等的元素的相对位置不变，即有 a = b，排序前a在b前面，那么排序后，a还是要在b前面。排序算法的稳定性是要看具体的算法实现，比如一般情况下，直接选择排序，快速排序，希尔排序，堆排序都不是稳定排序算法，基数排序，计数排序，归并排序，插入排序，冒泡排序都是稳定排序算法。

快速排序：A = {2， 2， 1}，排序后A = {1，2，2}。

希尔排序：A = {1，2，5，4，4，7}，排序后（k = 2）；A = {1， 2， 4， 4， 5， 7} 。

堆排序：A = {2，2，1}，排序后A = {1，2， 2}。

直接选择排序： A = {4， 4， 2， 5},排序后 A = {2，4， 4， 5}。

以上举例都不满足稳定性。