算法刷题系列（三）：排序——把无序问题变成有序结构

算法刷题系列（三）：排序——把无序问题变成有序结构

模拟和哈希表分别教我们按规则更新状态、用空间加速查找。本篇讨论另一种常见预处理：排序。排序不仅是把数据排成好看的顺序，它会建立单调性，让二分查找、双指针、区间扫描和贪心策略拥有可以利用的结构。

理解排序时，除了会调用库函数，还要知道比较规则、稳定性、是否修改输入，以及排序能否帮助当前问题。

一、先看排序能改变什么

有一组任务，每个任务有截止时间和名称：

(截止时间, 名称)
(5, "巡检")
(2, "备份")
(5, "发布")

按截止时间升序排列后，相近的时间会聚集在一起，后续便容易检查顺序、分组或寻找边界。若要求相同截止时间时保留原始先后关系，就需要稳定排序，或显式加入原始序号作为第二排序键。

二、常见复杂度与稳定性

实际刷题通常优先使用语言标准库排序。常见比较排序的时间复杂度为 O(n log n)；具体实现的稳定性和额外空间取决于语言与数据类型。

• 稳定排序：相等键的元素保留原有相对顺序。
• 原地排序：主要在输入数组内部重排，但具体额外空间仍依赖实现。
• 比较器：定义什么元素应该排在另一个元素前面；必须形成一致的顺序，不能随意违反传递性。

排序会改变原数组的顺序。如果之后还需要原始下标，应把值和下标绑定后排序，或先复制数据。

三、排序后如何衍生算法

排序常用于建立下列性质：

1. 相同值相邻：便于去重和频次分组。
2. 单调性：可以用二分查找定位第一个满足条件的位置。
3. 两端界限：在有序数组中，可用相向双指针寻找目标和。
4. 局部顺序：一些区间调度和贪心算法需要按起点、终点或权重排序。

排序本身不保证题目可以用贪心，也不一定总能降低复杂度。排序前要先说明它提供了什么可利用的信息。

四、Java：按多个字段排序

下面按截止时间升序排列；同一时间的任务按名称字典序排列。比较器使用 comparingInt，避免通过 a - b 比较时发生整数溢出。

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class SortingTasks {
    static final class Task {
        final int deadline;
        final String name;

        Task(int deadline, String name) {
            this.deadline = deadline;
            this.name = name;
        }

        @Override
        public String toString() {
            return "(" + deadline + ", " + name + ")";
        }
    }

    public static List<Task> sortedCopy(List<Task> tasks) {
        if (tasks == null) {
            throw new IllegalArgumentException("tasks must not be null");
        }

        List<Task> result = new ArrayList<>(tasks);
        result.sort(
            Comparator.comparingInt((Task task) -> task.deadline)
                .thenComparing(task -> task.name)
        );
        return result;
    }
}

Java 对象列表排序是稳定的；但这里由于名称作为第二键，截止时间相同但名称不同的元素仍会按名称重新排列。如果需要完全保留相同截止时间的输入顺序，只按 deadline 排序即可。

五、Python：按键排序与稳定性

def sorted_tasks(tasks: list[tuple[int, str]]) -> list[tuple[int, str]]:
    if tasks is None:
        raise ValueError("tasks must not be None")
    return sorted(tasks, key=lambda task: (task[0], task[1]))

tasks = [(5, "巡检"), (2, "备份"), (5, "发布")]
assert sorted_tasks(tasks) == [(2, "备份"), (5, "发布"), (5, "巡检")]
assert tasks == [(5, "巡检"), (2, "备份"), (5, "发布")]

Python 的 sorted 返回新列表，且是稳定排序；list.sort 则原地修改列表。上例的键包含两个字段，因此同截止时间时按名称排序。如果只用 key=lambda task: task[0]，同截止时间元素会保留输入顺序。

六、边界与比较器陷阱

1. 空数组或只有一个元素：无需特殊排序逻辑，标准库可以正确处理。
2. 比较函数直接做减法：a - b 可能溢出；使用语言提供的比较函数或键函数。
3. 排序稳定性误用：若需要保留同键输入顺序，要确认算法稳定或加入原始序号。
4. 排序后丢失下标：把 (value, index) 一起排序，或维护原数组副本。
5. 比较条件不一致：比较器必须保持传递性；不一致的规则可能让结果不可预测。
6. 盲目排序：若题目要求维持输入顺序，或只需一次线性判断，排序可能既多余又破坏信息。

七、与后续主题的连接

排序让数据有序，但要在有序序列中准确找到边界，还需要二分查找。后续双指针和 N 数之和也会使用排序提供的单调性。遇到排序题时，先问自己：排序之后，哪些原本无法快速判断的关系变得单调、相邻或可去重？

小结

排序是建立结构的预处理。熟悉稳定性、输入是否被修改、比较器一致性和下标保留方式，才能安全地把排序与二分、双指针或贪心结合。不要只看到“无序”就排序，要说明排序如何服务后续步骤。