关于常见排序的稳定性

关于常见排序的稳定性

关于常见排序的稳定性

1.冒泡排序

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

2.插入排序

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

3.选择排序

4.归并排序

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

5.快速排序

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

6.堆排序

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

7.希尔排序

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

8.基数排序

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

9.桶排序

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

10.计数排序

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。