排序方法稳定性总结

排序方法稳定性总结

文章目录

• 前言
• 一、排序算法稳定性是什么？
• 二、各个算法解析
• • 1.选择排序
  • 2.冒泡排序
  • 3.插入排序
  • 4. 归并排序
  • 5.快速排序
  • 6.堆排序
  • 7.桶排序思想的算法
• 总结

---

前言

这次将介绍各种排序算法的稳定性和一些小结论

---

一、排序算法稳定性是什么？

它说的是，当一个排序算法对一个数组排序的时候，两个相同的数，在排序后相对位置有没有发生变化。没有则稳定

二、各个算法解析 1.选择排序

选择排序算法是不稳定的，它是先遍历一次数组，找到一个最小值，和已排好序的边界后一个元素交换。这个交换的步骤就让选择排序变得不稳定。如果交换过去的数，在交换的过程中有相同的值，就会不稳定。

2.冒泡排序 冒泡排序是稳定的，因为它不涉及大范围交换，当然得有一个注意的地方，就是当不断比较的时候，当发现相等的时候不能交换。

也就是说他可以不稳定也可以稳定，但是何必让它不稳定呢？只不过是相等的时候不交换罢了

3.插入排序 插入排序是稳定的，就像冒泡排序一样，只要在比较到想的的时候不要交换就行。我们何必要它不稳定呢? 4. 归并排序 归并排序是稳定的，它有点类似上面两个排序，在merge的时候，也就是归并的时候，两个部分，当发现相等的时候，先让左边的赋值到辅助空间就行，要注意的是，小和问题不是稳定的，它是先让后面部分进行赋值。 5.快速排序 快速排序不是稳定，关键在partition的过程，也就是左右移动找到区分值的时候，一旦找到就得进行大范围的交换，一旦交换的距离中有相等的数值，就会出现稳定性不稳定的问题 6.堆排序 堆排序显然不可能是稳定的，甚至还没有排序，在建立堆的过程中就不稳定了，他将实现大范围的交换，并且还是跳跃式的，一旦中间有相等值，就会出现稳定性不稳定的问题 7.桶排序思想的算法

稳定，所有桶排序的算法都是稳定的，因为它本身定义了遍历顺序，还有桶本身是有稳定性问题的

---

总结 稳定的排序：冒泡，插入，归并，桶排序 不稳定的排序：快速，堆，插入