排序算法的关键指标

raw/articles/2026/05/排序基础

一句话总结

介绍排序算法的三个核心评估指标：时空复杂度、排序稳定性和是否原地排序，为后续学习具体排序算法打下基础。

核心要点

1. 时空复杂度

排序算法的效率由时间复杂度和空间复杂度共同衡量。时间复杂度描述算法执行时间随输入规模增长的趋势，空间复杂度描述算法占用额外存储空间的情况。复杂度越低，算法性能越好。

2. 排序稳定性

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

实际意义：

• 对于简单 int 数组排序，稳定性意义不大
• 对于复杂数据结构（如订单数据），稳定排序能保持多字段排序的层次性

实例说明： 假设已有按日期排序的订单数据，现需按用户 ID 排序：

• 使用稳定排序：相同用户 ID 的订单仍按日期有序排列
• 使用不稳定排序：相同用户 ID 的订单相对位置可能变化，日期有序性丧失

3. 是否原地排序

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

区别示例：

// 非原地排序：需要 O(N) 额外空间
void sort(int[] nums) {
    int[] tmp = new int[nums.length]; // 辅助数组
    // 对 nums 进行排序
    for ...
}

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

优势：对于大数据量的排序，原地排序算法在内存使用上更有优势。

相关概念

• 时间复杂度：描述算法执行时间随输入规模增长的渐近趋势
• 空间复杂度：描述算法占用额外存储空间随输入规模增长的渐近趋势
• 排序稳定性：稳定排序保持相同元素相对位置不变，适用于多字段排序场景
• 原地排序：只需常数级额外空间、直接操作原数组的排序方式

相关实体

• labuladong：算法学习平台 labuladong.online 作者

总结

排序算法的评估应从三个维度综合考虑：时空复杂度（效率）、稳定性（多字段排序的有序性保持）、是否原地排序（内存使用效率）。这三个指标将用于分析后续学习的具体排序算法。