稳定排序算法有哪些

相信您已经掌握了很多种排序算法，比如冒泡排序、插入排序、希尔排序、选择排序等。这些排序算法中，有些是 "稳定" 的，有些是 "不稳定" 的。

给定的待排序序列中，经常会包含相同的元素，例如：

3 1 2 4 2

此序列中包含两个元素 2，为了区分它们，我们分别称它们为 "红 2" 和 "绿 2"。

评价一个排序算法是否稳定，是指该算法完成排序的同时，是否会改变序列中相同元素的相对位置。例如，上面序列中红 2 和绿 2 的相对位置是：红 2 位于绿 2 的左侧，或者说绿 2 位于红 2 的右侧。如果使用某个排序算法对序列进行排序，得到的有序序列是：

升序序列：
1 2 2 3 4
降序序列：
4 3 2 2 1

红 2 依然位于绿 2 的左侧，这个排序算法就是稳定的；反之，如果红 2 和绿 2 的相对位置发生了改变，这个排序算法就是不稳定的。

下表给大家列出了常用的排序算法以及它们的稳定性：

表 1 排序算法的稳定性

排序算法	稳定排序算法
冒泡排序算法	稳定
插入排序算法	稳定
希尔排序算法	不稳定
选择排序算法	不稳定
归并排序算法	稳定
快速排序算法	不稳定
计数排序算法	不稳定
基数排序算法	不稳定
桶排序算法	不稳定

通过优化代码、改进实现思路等方式，某些 "不稳定" 的算法也可以变得 "稳定"。以桶排序算法为例，如果保证各个桶内存储相同元素时不改变它们的相对位置，且桶内排序时采用稳定的排序算法，那么桶排序算法就可以变得“稳定”。

【扩展】就地排序算法

除了稳定性，某些场景中还需要使用就地排序算法。

“就地排序”的含义是：排序算法在排序过程中，主要使用待排序序列占用的内存空间，最多额外创建几个辅助变量，不再申请过多的辅助空间。也就是说，就地排序算法指的是直接将待排序序列修改成有序序列的排序算法，而不是新创建一个有序序列。

就地排序算法的空间复杂度为 O(1)。

下表给大家罗列了哪些排序算法属于就地排序算法：

表 2 就地排序算法

排序算法	就地排序算法
冒泡排序算法	是
插入排序算法	是
希尔排序算法	是
选择排序算法	是
归并排序算法	不是
快速排序算法	是
计数排序算法	不是
基数排序算法	不是
桶排序算法	不是