🍕 总结排序(时间复杂度, 空间复杂度, 稳定性)
下面指的都是基于数组结构的排序。
排序算法(典型) | 时间复杂度(通常情况) | (额外)空间复杂度(通常情况) | 稳定性(通常情况) |
---|---|---|---|
选择排序 | ❌不稳定 | ||
冒泡排序 | ✔️稳定 | ||
插入排序 | ✔️稳定 | ||
归并排序 | ✔️稳定 | ||
随机快速排序 | ❌不稳定 | ||
堆排序 | ❌不稳定 | ||
计数排序 | ✔️稳定 | ||
基数排序 | ✔️稳定 |
稳定性
稳定就是: 当存在相等元素时, 排序后它们的相对顺序不变。
选择排序: 每次选择最小的数与第一个数交换。
- 排序后不稳定🌰:
- [
, , 1 ] - [ 1,
, ] 第一轮遍历时, 选到最小值 1, 将它与第一个数交换 - 很明显, 排序后的
和 位置互换了。
- [
- 排序后不稳定🌰:
冒泡排序: 如果左值 > 右值, 就交换。
- 排序后稳定🌰:
- [
, , 1 ] - [
, 1, ] - [ 1,
, ]
- [
- 注意⚠️, 如果冒泡排序的实现写成左值 >= 右值时交换, 则冒泡排序会变成不稳定:
- [
, ] - [
, ] 因为此时左值 == 右值, 所以还会继续交换, 此时就会导致不稳定
- [
- 排序后稳定🌰:
插入排序: 当左值 >= 右值时, 停止插入(交换)。
- 排序后稳定🌰:
- [
, , 1 ] - [
, 1, ] - [ 1,
, ]
- [
- 同样注意⚠️, 如果当两个值相等时, 还要继续插入, 则会变成不稳定:
- [
, 1, ] - [ 1,
, ] 插好 1 - [ 1,
, ] 插好 - [ 1,
, ] 插好
- [
- 排序后稳定🌰:
归并排序: 先二分后依次排序, 然后合并。 合并过程中若两个数相等, 先合并左边
- 排序后稳定🌰:
- merge [ 1,
] [ ] - merge result: [ 1 ]
- merge result: [ 1,
] - merge result: [ 1,
, ]
- merge [ 1,
- 同样注意⚠️, 如果先合并右边, 则会不稳定。 而前面介绍过的 "小和问题", 就是先合并右边的, 所以那时的归并是不稳定的
- merge [ 1,
] [ ] - merge result: [ 1 ]
- merge result: [ 1,
] - merge result: [ 1,
, ]
- merge [ 1,
- 排序后稳定🌰:
快速排序: 不断的随机选取 pivot(划分值), 然后执行 partition。partition 核心: 将数值划分进对应区域。 比如, 将 < pivot 的值划分进 "< 区", 具体做法是将该值域 "< 区" 边界交换, 然后扩大边界。
- 排序后不稳定🌰:
- [
, , 1 ], 选取的 pivot 是 2 - [ 1,
, ], 识别到 1 时, 将它与 "< 区" 的边界+1 值交换, 故 跨过了
- [
- 不管是二项划分还是三项划分, 结果都是不稳定的。
- 排序后不稳定🌰:
堆排序: 利用堆的特性(可以是大根堆或小根堆)进行排序
- 在构造堆的过程中就已经打乱了顺序, 举个小根堆打乱🌰:
- 原数组: [
, , 1 ] - 对 1 进行 heap insert (或者对
进行 heapify) 的过程中, 将会交换 1 和 的位置, 结果如下 - 小根堆: [ 1,
, ]
- 原数组: [
- 在构造堆的过程中就已经打乱了顺序, 举个小根堆打乱🌰:
计数排序, 基数排序, 他们的算法思路本身就不是基于比较的, 他们是利用 "桶" 的结构来实现排序的, 所以只要确保 "入桶" 和 "出桶" 的过程中元素的相对顺序不变, 那么他们就是稳定的
总结
前面的几种排序, 可以分为三大类, 选择冒泡插入作为一类, 归并快排堆作为一类, 计数基数作为一类。 对于计数和基数排序, 只适用于特定情况。 选择冒泡插入排序, 可以作为简单排序算法的学习, 只适用简单数据。 归并快排堆排序, 适用范围最广。
归并, 快排, 堆 如何选取?
- 一般都是选择 随机快排 进行排序。 虽然快排和堆的时间复杂度相同, 但实践过程中发现快排的常数时间更短。
- 当有稳定性需求时, 选择归并排序
- 当要压榨空间时, 选择堆排序
排序算法常见的坑
- 归并排序的额外空间复杂度可以变成 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 个, 则使用的是插入排序。
稳定性问题。 对于基本数据, 不需要考虑稳定性问题。 比如系统提供的排序黑盒, 当数据是基本类型时, 它会使用快排。 但数据是对象时, 它会使用归并。