🍕 总结排序(时间复杂度, 空间复杂度, 稳定性)

下面指的都是基于数组结构的排序。

排序算法(典型)	时间复杂度(通常情况)	(额外)空间复杂度(通常情况)	稳定性(通常情况)
选择排序	$O(N^2)$	$O(1)$	❌不稳定
冒泡排序	$O(N^2)$	$O(1)$	✔️稳定
插入排序	$O(N^2)$	$O(1)$	✔️稳定
归并排序	$O(N\ast logN)$	$O(N)$	✔️稳定
随机快速排序	$O(N\ast logN)$	$O(logN)$	❌不稳定
堆排序	$O(N\ast logN)$	$O(1)$	❌不稳定
计数排序	$O(N)$	$O(N)$	✔️稳定
基数排序	$O(N)$	$O(N)$	✔️稳定

稳定性

稳定就是: 当存在相等元素时, 排序后它们的相对顺序不变。

• 选择排序: 每次选择最小的数与第一个数交换。

  • 排序后不稳定🌰:
    • [ $3_a$, $3_b$, 1 ]
    • [ 1, $3_b$, $3_a$ ] 第一轮遍历时, 选到最小值 1, 将它与第一个数交换
    • 很明显, 排序后的 $3_b$ 和 $3_a$ 位置互换了。

• 冒泡排序: 如果左值 > 右值, 就交换。

  • 排序后稳定🌰:
    • [ $3_a$, $3_b$, 1 ]
    • [ $3_a$, 1, $3_b$ ]
    • [ 1, $3_a$, $3_b$ ]
  • 注意⚠️, 如果冒泡排序的实现写成左值 >= 右值时交换, 则冒泡排序会变成不稳定：
    • [ $3_a$, $3_b$ ]
    • [ $3_b$, $3_a$ ] 因为此时左值 == 右值, 所以还会继续交换, 此时就会导致不稳定

• 插入排序: 当左值 >= 右值时, 停止插入(交换)。

  • 排序后稳定🌰:
    • [ $3_a$, $3_b$, 1 ]
    • [ $3_a$, 1, $3_b$ ]
    • [ 1, $3_a$, $3_b$ ]
  • 同样注意⚠️, 如果当两个值相等时, 还要继续插入, 则会变成不稳定：
    • [ $3_a$, 1, $3_b$ ]
    • [ 1, $3_a$, $3_b$ ] 插好 1
    • [ 1, $3_a$, $3_b$ ] 插好 $3_a$
    • [ 1, $3_b$, $3_a$ ] 插好 $3_b$

• 归并排序: 先二分后依次排序, 然后合并。 合并过程中若两个数相等, 先合并左边

  • 排序后稳定🌰:
    • merge [ 1, $3_a$ ] [ $3_b$ ]
    • merge result: [ 1 ]
    • merge result: [ 1, $3_a$ ]
    • merge result: [ 1, $3_a$, $3_b$ ]
  • 同样注意⚠️, 如果先合并右边, 则会不稳定。 而前面介绍过的 "小和问题", 就是先合并右边的, 所以那时的归并是不稳定的
    • merge [ 1, $3_a$ ] [ $3_b$ ]
    • merge result: [ 1 ]
    • merge result: [ 1, $3_b$ ]
    • merge result: [ 1, $3_b$, $3_a$ ]

• 快速排序: 不断的随机选取 pivot(划分值), 然后执行 partition。partition 核心: 将数值划分进对应区域。 比如, 将 < pivot 的值划分进 "< 区", 具体做法是将该值域 "< 区" 边界交换, 然后扩大边界。

  • 排序后不稳定🌰:
    • [ $3_a$, $3_b$, 1 ], 选取的 pivot 是 2
    • [ 1, $3_b$, $3_a$ ], 识别到 1 时, 将它与 "< 区" 的边界+1 值交换, 故 $3_a$ 跨过了 $3_b$
  • 不管是二项划分还是三项划分, 结果都是不稳定的。

• 堆排序: 利用堆的特性(可以是大根堆或小根堆)进行排序

  • 在构造堆的过程中就已经打乱了顺序, 举个小根堆打乱🌰:
    • 原数组: [ $3_a$, $3_b$, 1 ]
    • 对 1 进行 heap insert (或者对 $3_a$ 进行 heapify) 的过程中, 将会交换 1 和 $3_a$ 的位置, 结果如下
    • 小根堆: [ 1, $3_b$, $3_a$ ]

• 计数排序, 基数排序, 他们的算法思路本身就不是基于比较的, 他们是利用 "桶" 的结构来实现排序的, 所以只要确保 "入桶" 和 "出桶" 的过程中元素的相对顺序不变, 那么他们就是稳定的

总结

前面的几种排序, 可以分为三大类, 选择冒泡插入作为一类, 归并快排堆作为一类, 计数基数作为一类。 对于计数和基数排序, 只适用于特定情况。 选择冒泡插入排序, 可以作为简单排序算法的学习, 只适用简单数据。 归并快排堆排序, 适用范围最广。

归并, 快排, 堆 如何选取?

• 一般都是选择 随机快排 进行排序。 虽然快排和堆的时间复杂度相同, 但实践过程中发现快排的常数时间更短。
• 当有稳定性需求时, 选择归并排序
• 当要压榨空间时, 选择堆排序

排序算法常见的坑

• 归并排序的额外空间复杂度可以变成 O(1)。—— 非常难实现, 不需要掌握。有兴趣可以搜索"归并排序 内部缓存法"。 而且虽然空间复杂度降了, 但同时它也变得不稳定了, 那为什么不用堆排序呢?
• 原地归并排序可以实现空间复杂度为 O(1)。—— 虽然空间复杂度降低了, 但它的时间复杂度变成了 O(N^2), 那为什么不用简单排序呢
• 快速排序可以做到稳定。 —— 难。 而且虽然做到了稳定性, 但空间复杂度会变成 O(N), 那为什么不用归并排序呢? 有兴趣可以搜索 "01 stable sort"。
• 面试题: 要求奇数放在数组左边, 偶数放在数组右边, 同时相对次序不变, 并且时间复杂度为 O(N), 空间复杂度为 O(1)。
  • 回答: 经典的快排做不到稳定性, 而经典快排的 partition 又是 01 标准的, 它和这个奇偶问题其实是一种调整策略, 快排做不到, 所以我也不知道怎么做。 然后把问题反抛给面试官。
  • partition 过程, 能够将 "≤ pivot" 的放左边, "> pivot" 的放右边, 这其实就是 "01标准"。 它能做到时间复杂度 O(N), 空间复杂度 O(1), 但它做不到稳定。 所以这道面试题目前是无解的。

工程上对排序的改进

• 充分利用 O(N*logN) 和 O(N^2) 各自的优势。 比如在大数据量的时候使用快排, 在小数据量的时候使用插入。 所以在快排的代码上, 经常会看到在排序前, 先用 if 判断一下待排序的数据, 如果小于一定 60 个, 则使用的是插入排序。

• 稳定性问题。 对于基本数据, 不需要考虑稳定性问题。 比如系统提供的排序黑盒, 当数据是基本类型时, 它会使用快排。 但数据是对象时, 它会使用归并。