关于常见排序的稳定性

1.冒泡排序

显然对于两个相邻且相同的元素，不会交换相对位置，因此是稳定的。

2.插入排序

插排也是基于相邻元素交换，所以也是稳定的。

3.选择排序

可能存在选择第$i$小的元素时，把原本相同的元素的相对位置破坏了。

4.归并排序

合并时，不改变相对顺序，因为是左边+右边拼接。

5.快速排序

选择的基数的不同，可能会导致排序结果不同，相同元素的相对性被破坏。

6.堆排序

堆排序不稳定，因为堆上的操作可以更改相等项目的相对顺序。

7.希尔排序

本质就是分组插入排序，组内相对顺序不变，组间相对顺序可能变化了，所以不稳定。

8.基数排序

稳定的，最开始会将下标作为第二关键字。

9.桶排序

稳定的，同基数排序一样。

10.计数排序

稳定的，开了辅助数组记录每个数出现的次数，计数排序不是基于元素比较,而是利用数组下标来确定元素的正确位置。