排序算法的关键指标

时空复杂度

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

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

排序稳定性

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

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

如果单单排序 int 数组，那么稳定性没有什么意义。但如果排序一些结构比较复杂的数据，那么稳定排序就会有一定的优势。

比如说现在你有若干订单数据，已经按照交易日期排好序了，现在你想对用户 ID 再进行排序，
如果你用稳定排序算法，那么排序完成后，相同用户 ID 的订单依然会按照交易日期有序排列

是否原地排序

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

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

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

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

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

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