排序算法的稳定性及其汇总

稳定性：值相同的元素在排序完成后能否保住原先的相对顺序不变

同样值的个体之间，如果不因为排序而改变相对次序，就是这个排序是有稳定性的；否则就没有。

  • 不具备稳定性的排序：

选择排序、快速排序、堆排序

  • 具备稳定性的排序：

冒泡排序、插入排序、归并排序、一切桶排序思想下的排序

目前没有找到时间复杂度 总结 - 图1，额外空间复杂度 总结 - 图2，又稳定的排序。

常见的坑

  1. 归并排序的额外空间复杂度可以变成 总结 - 图3，但是非常难，不需要掌握，有兴趣可以搜 归并排序内部缓存法，但是不再稳定。如果是这样为什么不用堆排序呢？
  2. 原地归并排序 的帖子都是垃圾，会让归并排序的时间复杂度变成 总结 - 图4
  3. 快速排序可以做到稳定性问题，但是非常难，不需要掌握，可以搜 01 stable sort，但是会让快排的空间复杂度变成 总结 - 图5，可以使用归并排序
  4. 所有的改进都不重要，因为目前没有找到时间复杂度 总结 - 图6，额外空间复杂度 总结 - 图7，又稳定的排序。
  5. 有一道题目，是奇数放在数组左边，偶数放在数组右边，还要求原始的相对次序不变，碰到这个问题，快排是无解的，做不到稳定性

工程上对排序的改进

  • 充分利用 总结 - 图8 和 总结 - 图9 排序各自的优势
  • 稳定性的考虑

例如：在快排或者归并中，在数组 partition 范围较小后，做插入排序

  1. public static void partition(int[] arr, int L, int R) {
  2.     if (L >= R) return;
  3.     if (R - L < 60) {
  4.         // 做插入排序
  5.     }
  6.     ……
  7. }