排序算法的关键指标

一般刷题和面试/笔试的时候不会直接让你手撕排序算法，不过考虑到知识的完整性，我这里还是开一个章节，结合 可视化面板 讲解几种常见排序算法的原理、特点、时间复杂度和代码实现。

本文先介绍一下排序算法的几个关键指标，后面讲解到具体的排序算法时，都会根据这些指标来分析。

时空复杂度

首先一个指标肯定是时间复杂度和空间复杂度。

正如 时空复杂度入门 中所说，对于任意一个算法，其时间复杂度和空间复杂度都是越小越好的。

排序稳定性

稳定性是排序算法的一个重要性质，我们可以简单总结为：

对于序列中的相同元素，如果排序之后它们的相对位置没有发生改变，则称该排序算法为「稳定排序」，反之则为「不稳定排序」。

如果单单排序 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 的订单相对位置可能变化，所以对于相同用户 ID 的订单，交易日期的有序性会丧失，相当于你之前对日期的排序白做了。

可以看到，稳定性是个很重要的性质，所以你在使用排序算法时要特别注意，避免出现预期之外的结果。

是否原地排序

原地排序就是指排序过程中不需要额外的辅助空间，只需要常数级别的额外空间，直接操作原数组进行排序。

注意，关键是是否需要额外的空间，而不是是否返回一个新的数组。具体来说就是类似这样的区别：

// 非原地排序
void sort(int[] nums) {
    // 排序过程中需要额外的辅助数组，消耗 O(N) 的空间
    int[] tmp = new int[nums.length];

    // 对 nums 进行排序
    for ...
}

// 原地排序
void sort(int[] nums) {
    // 直接操作 nums，不需要额外的辅助数组，消耗 O(1) 的空间
    for ...
}

不难想到，对于大数据量的排序，原地排序算法是比较有优势的。

排序算法的几个关键指标就是这些，后面我会介绍几种常见的排序算法，都会根据这些指标来分析它们的优劣。