排序算法的关键指标
一般刷题和面试/笔试的时候不会直接让你手撕排序算法,不过考虑到知识的完整性,我这里还是开一个章节,结合 可视化面板 讲解几种常见排序算法的原理、特点、时间复杂度和代码实现。
本文先介绍一下排序算法的几个关键指标,后面讲解到具体的排序算法时,都会根据这些指标来分析。
时空复杂度
首先一个指标肯定是时间复杂度和空间复杂度。
正如 时空复杂度入门 中所说,对于任意一个算法,其时间复杂度和空间复杂度都是越小越好的。
排序稳定性
稳定性是排序算法的一个重要性质,我们可以简单总结为:
对于序列中的相同元素,如果排序之后它们的相对位置没有发生改变,则称该排序算法为「稳定排序」,反之则为「不稳定排序」。
如果单单排序 int 数组,那么稳定性没有什么意义。但如果排序一些结构比较复杂的数据,那么稳定性排序就会有一定的优势。
比如说现在你有若干订单数据,已经按照交易日期排好序了,现在你想对用户 ID 再进行排序,这样一来相同用户 ID 的订单就会聚集在一起,方便查看。稳定排序和不稳定排序的区别就体现在这里:
如果你用稳定排序算法,那么排序完成后,相同用户 ID 的订单依然会按照交易日期有序排列:
Date UserID
2020-02-01 1001
2020-02-02 1001
2020-02-03 1001
2020-01-01 1002
2020-01-02 1002
2020-01-03 1002
...
因为之前已经按照日期排好序了,稳定排序之后,相同用户 ID 的订单的相对位置保持不变,所以在日期上依然是有序的。
如果你用不稳定排序算法,相同用户 ID 的订单相对位置可能变化,所以对于相同用户 ID 的订单,交易日期的有序性会丧失。
可以看到,稳定性是个很重要的性质,所以你在使用排序算法时要特别注意,避免出现预期之外的结果。
是否原地排序
原地排序就是指排序过程中不需要额外的辅助空间,只需要常数级别的额外空间,直接操作原数组进行排序。
注意,关键是是否需要额外的空间,而不是是否返回一个新的数组。具体来说就是类似这样的区别:
// 非原地排序
void sort(int[] nums) {
// 排序过程中需要额外的辅助数组,消耗 O(N) 的空间
int[] tmp = new int[nums.length];
// 对 nums 进行排序
for ...
}
// 原地排序
void sort(int[] nums) {
// 直接操作 nums,不需要额外的辅助数组,消耗 O(1) 的空间
for ...
}
不难想到,对于大数据量的排序,原地排序算法是比较有优势的。
排序算法的几个关键指标就是这些,后面我会介绍几种常见的排序算法,都会根据这些指标来分析它们的优劣。