3. 排序规则实现：插入排序、阻塞合并、时间戳与优先级混合排序

通知队列的排序直接决定用户看到的通知顺序。Android SystemUI 采用三类排序规则：

• 插入排序（Insertion Sort） — 新通知到达时，按既定优先级插入当前位置。
• 阻塞合并（Blocking Merge） — 将来自同一应用或同一分组的多个通知合并为一块，避免穿插。
• 时间戳与优先级混合排序（Timestamp-Priority Hybrid） — 同时考虑发布时间和通知优先级，实现按实际重要性排序。

3.1 排序规则架构

SystemUI 的 NotificationSorter 管理所有排序逻辑。排序器内部维护一个 RankingMap，排序规则以策略模式注入。

3.2 插入排序实现

插入排序用于通知加入队列的瞬间。SystemUI 不整体重排，而是在新通知到达时找到正确插入点。

步骤	操作	时间复杂度
1	获取新通知的优先级和时间戳	O(1)
2	从队列尾部向前扫描，找到第一个“比新通知更差”的位置	O(n)
3	执行插入操作，更新索引	O(1)

// NotificationSorter.java — 插入排序核心
private int findInsertIndex(@NonNull List<NotificationEntry> entries,
                            @NonNull NotificationEntry newEntry) {
    long newTime = newEntry.getSbn().getPostTime();
    int newPriority = newEntry.getSbn().getNotification().priority;

    for (int i = entries.size() - 1; i >= 0; i--) {
        NotificationEntry existing = entries.get(i);
        long existTime = existing.getSbn().getPostTime();
        int existPriority = existing.getSbn().getNotification().priority;

        // 时间戳优先，相同时间下高优先级排前
        if (existTime > newTime ||
           (existTime == newTime && existPriority < newPriority)) {
            return i + 1;
        }
    }
    return 0;
}

3.3 阻塞合并规则

阻塞合并用于将来自同一应用或同一分组（GroupKey）的通知合并为一个“块”。合并后的块在 UI 上折叠显示，排序时作为一个整体参与。

• GroupKey 哈希：以 packageName + groupKey 作为唯一标识。
• 块头选择：块内最新通知作为代表，整体排序依据该代表的时间戳和优先级。
• 块内有序：块内通知按时间戳降序排列。

// BlockingMergePolicy.java — 合并分组
public List<NotificationBlock> merge(List<NotificationEntry> entries) {
    Map<String, NotificationBlock> blockMap = new LinkedHashMap<>();
    for (NotificationEntry entry : entries) {
        String groupKey = entry.getSbn().getGroupKey();
        if (groupKey == null) {
            // 无分组的通知自成一块
            groupKey = entry.getSbn().getPackageName() + ":singleton";
        }
        NotificationBlock block = blockMap.get(groupKey);
        if (block == null) {
            block = new NotificationBlock(groupKey);
            blockMap.put(groupKey, block);
        }
        block.addEntry(entry);
    }
    // 每块内部按时间降序
    for (NotificationBlock block : blockMap.values()) {
        block.sortEntriesByTimeDescending();
    }
    return new ArrayList<>(blockMap.values());
}

3.4 时间戳与优先级混合排序

混合排序在块级进行。SystemUI 使用自定义 Comparator，权重公式为：

score = (currentTime - postTime) * WEIGHT_TIME + priority * WEIGHT_PRIORITY
// 默认 WEIGHT_TIME = 1.0, WEIGHT_PRIORITY = 0.5

混合排序不改变块内顺序，只决定块在列表中出现的先后。

参数	含义	默认值	影响范围
postTime	通知发布时间（毫秒）	System.currentTimeMillis()	时效性
priority	通知优先级（-2 ～ 2）	0	重要程度
WEIGHT_TIME	时间权重系数	1.0	新旧差异幅度
WEIGHT_PRIORITY	优先级权重系数	0.5	优先级拉升效果

// HybridComparator.java — 混合排序比较器
@Override
public int compare(NotificationBlock a, NotificationBlock b) {
    long timeDelta = a.getRepresentative().getSbn().getPostTime()
                   - b.getRepresentative().getSbn().getPostTime();
    int priorityDelta = a.getRepresentative().getSbn().getNotification().priority
                      - b.getRepresentative().getSbn().getNotification().priority;

    double scoreA = -timeDelta * WEIGHT_TIME + priorityDelta * WEIGHT_PRIORITY;
    double scoreB = 0; // 以a为基准

    if (scoreA > 0) return -1;  // a 更靠前
    if (scoreA < 0) return 1;   // b 更靠前
    return 0;
}

3.5 调试与验证

排序规则可通过日志或 dumpsys 验证。

# 查看当前通知队列排序（使用 adb shell）
adb shell dumpsys notification --ranking

# 输出示例：
# Ranked notifications (visible):
#   [0] pkg=com.example.msg  postTime=1690000012345  priority=1  groupKey=chat:groupA
#   [1] pkg=com.example.news postTime=1690000020000  priority=-1 groupKey=news:singleton
#   [2] pkg=com.example.cal  postTime=1690000000000  priority=2  groupKey=calendar:reminder

如需调试排序计算过程，可在 NotificationSorter.java 中增加日志：

if (DEBUG) {
    Log.d("NotificationSorter",
          String.format("compare: a=%s(time=%d,pri=%d) b=%s(time=%d,pri=%d) result=%d",
                        a.getKey(), a.getSbn().getPostTime(), a.getSbn().getNotification().priority,
                        b.getKey(), b.getSbn().getPostTime(), b.getSbn().getNotification().priority,
                        cmpResult));
}

3.6 性能与稳定性优化

• 比较器缓存：对相同 NotificationEntry 对，缓存比较结果，避免重复计算时间戳和优先级。
• 惰性排序：仅在 UI 刷新或用户展开通知面板时才触发完整排序。
• 优先级溢出保护：当时间权重太大导致优先级几乎无效时，自动增大 WEIGHT_PRIORITY 至 1.0。
• 阻塞合并边界：单块通知超过 50 条时，强制分裂为子块，避免 UI 卡顿。

3.7 常见错误与解决方案

错误现象	根因	解决方案
同分组通知乱序	阻塞合并未正确识别 GroupKey	确认 GroupKey 的格式是否符合 packageName:groupKey
高优先级通知被排到后面	时间戳差异过大覆盖优先级	调整 WEIGHT_PRIORITY 系数
插入排序性能劣化	队列长度超过 200 条还在用 O(n) 插入	改用二分查找 + LinkedList 插入
合并后 UI 展开错误	块内排序与整体排序冲突	块内排序只影响展开顺序，整体排序只影响块位置