排序的稳定性

定义

• 稳定排序：如果原始序列中两个值相等的元素 A 和 B（满足 A = B），且 A 出现在 B 之前，排序后 A 仍然在 B 之前。
• 不稳定排序：排序后 A 和 B 的相对顺序可能发生改变。

示例

• 原始序列：[3, 2, 2*, 1] （2 和 2* 值相等但可区分）
• 稳定排序结果：[1, 2, 2*, 3]（两个 2 的相对顺序不变）
• 不稳定排序结果：[1, 2*, 2, 3]（2* 跑到了 2 前面）

评判方法

(1) 观察交换/移动规则

检查算法在比较和交换时如何处理相等元素：

• 稳定算法：当比较 arr[i] 和 arr[j] 且 arr[i] == arr[j] 时，不会交换它们的位置。
• 不稳定算法：可能交换相等元素的位置（即使它们原本有序）。

1
2
3
4
5
6
7
8

// 冒泡排序（稳定）的典型比较逻辑：
if (arr[j] > arr[j+1]) { // 仅当严格大于时交换
    swap(arr[j], arr[j+1]); // 相等时不交换 → 稳定
}

// 选择排序（不稳定）的典型逻辑：
minIndex = findMinIndex(); // 可能跳过前面的相等元素
swap(i, minIndex); // 可能破坏相等元素的顺序

(2) 形式化证明

通过数学归纳法或循环不变量证明：

• 定义不变条件：“排序过程中相等元素的相对顺序始终不变”
• 证明每一步操作（比较、交换）均保持该条件

(3) 构造反例测试

设计特定输入序列验证。

重要性

1. 多级排序：先按次要键排序，再按主要键排序时，需要保持次要键的顺序。
2. 数据可视化：当按新属性排序时，需保留原始视图中的部分顺序。
3. 事务处理：日志按时间戳排序后，相同时间戳的事件需保持原始提交顺序。