数据结构与算法 / 系统课时
算法正确性测试
算法正确性测试
实现能够编译、并在几个示例上得到正确结果,并不代表算法对全部输入都正确。本课建立示例测试、边界测试、随机差分测试和性质测试组成的验证链,并用固定随机种子得到可复现的 Java 测试结果。
学习目标
- 能为算法设计正常输入、边界输入和退化输入。
- 能使用参考实现进行随机差分测试,并复现失败样例。
- 能用排序性、元素守恒等性质检查没有固定答案的大量输入。
四层测试策略
示例测试验证题目给出的典型路径,边界测试覆盖空输入、单元素、重复值和极端顺序。随机差分测试把待测实现与可信参考实现放在同一批输入上比较;性质测试则不依赖完整答案,而是检查结果必须满足的不变量。

| 测试层次 | 主要目的 | 关键做法 |
|---|---|---|
| 示例测试 | 验证已知主路径 | 为典型输入写出精确期望值 |
| 边界测试 | 暴露下标和条件错误 | 覆盖空数组、单元素、重复值、已排序和逆序 |
| 随机差分测试 | 扩大输入覆盖面 | 使用固定种子生成输入,并与 Arrays.sort 比较 |
| 性质测试 | 检查结果不变量 | 同时验证非递减顺序与元素多重集合不变 |
排序算法只检查“结果有序”还不够,因为错误实现可能通过丢弃元素得到一个有序数组。因此至少同时验证:相邻元素非递减,以及排序前后每个值的出现次数完全一致。
完整可运行示例
将下面代码保存为 AlgorithmCorrectnessTest.java。示例测试一个插入排序实现,其中随机测试使用固定种子,因此任何失败都能在下一次运行中复现。
java
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
public class AlgorithmCorrectnessTest {
public static void main(String[] args) {
runExampleTests();
runBoundaryTests();
runRandomDifferentialTests();
runPropertyTests();
System.out.println("全部测试通过");
}
private static void runExampleTests() {
assertSortEquals(
new int[]{5, 1, 4, 2, 8},
new int[]{1, 2, 4, 5, 8}
);
assertSortEquals(
new int[]{3, -1, 3, 0},
new int[]{-1, 0, 3, 3}
);
assertSortEquals(
new int[]{2, 1},
new int[]{1, 2}
);
System.out.println("示例测试通过:3 组");
}
private static void runBoundaryTests() {
assertSortEquals(new int[]{}, new int[]{});
assertSortEquals(new int[]{7}, new int[]{7});
assertSortEquals(new int[]{4, 4, 4}, new int[]{4, 4, 4});
assertSortEquals(new int[]{1, 2, 3, 4}, new int[]{1, 2, 3, 4});
assertSortEquals(new int[]{4, 3, 2, 1}, new int[]{1, 2, 3, 4});
System.out.println("边界测试通过:5 组");
}
private static void runRandomDifferentialTests() {
Random random = new Random(20260803L);
for (int round = 0; round < 500; round++) {
int[] actual = randomArray(random, 30);
int[] expected = actual.clone();
// 使用标准库排序作为本轮测试的参考实现。
Arrays.sort(expected);
insertionSort(actual);
assertArrayEquals(expected, actual);
}
System.out.println("随机差分测试通过:500 组");
}
private static void runPropertyTests() {
Random random = new Random(1803L);
for (int round = 0; round < 500; round++) {
int[] data = randomArray(random, 40);
int[] original = data.clone();
insertionSort(data);
// 两个性质共同防止“有序但丢元素”的伪正确结果。
assertNonDecreasing(data);
assertSameMultiset(original, data);
}
System.out.println("性质测试通过:500 组");
}
private static int[] randomArray(Random random, int maxLength) {
int length = random.nextInt(maxLength + 1);
int[] data = new int[length];
for (int i = 0; i < length; i++) {
data[i] = random.nextInt(101) - 50;
}
return data;
}
private static void insertionSort(int[] data) {
for (int i = 1; i < data.length; i++) {
int value = data[i];
int j = i - 1;
while (j >= 0 && data[j] > value) {
data[j + 1] = data[j];
j--;
}
data[j + 1] = value;
}
}
private static void assertSortEquals(int[] input, int[] expected) {
int[] actual = input.clone();
insertionSort(actual);
assertArrayEquals(expected, actual);
}
private static void assertArrayEquals(int[] expected, int[] actual) {
if (!Arrays.equals(expected, actual)) {
throw new AssertionError(
"期望 " + Arrays.toString(expected)
+ ",实际 " + Arrays.toString(actual)
);
}
}
private static void assertNonDecreasing(int[] data) {
for (int i = 1; i < data.length; i++) {
if (data[i - 1] > data[i]) {
throw new AssertionError("结果不是非递减序列");
}
}
}
private static void assertSameMultiset(int[] before, int[] after) {
Map<Integer, Integer> counts = new HashMap<>();
for (int value : before) {
counts.merge(value, 1, Integer::sum);
}
for (int value : after) {
counts.merge(value, -1, Integer::sum);
}
for (int count : counts.values()) {
if (count != 0) {
throw new AssertionError("排序前后的元素及其出现次数不一致");
}
}
}
}使用 JDK 17 或更高版本编译并运行:
bash
javac AlgorithmCorrectnessTest.java
java AlgorithmCorrectnessTest预期输出
text
示例测试通过:3 组
边界测试通过:5 组
随机差分测试通过:500 组
性质测试通过:500 组
全部测试通过常见错误与练习
常见错误
- 只测试一个正常示例,会遗漏空数组、重复元素和逆序输入导致的边界错误。
- 随机测试不固定种子,失败后无法生成同一输入,修复过程会变得不可重复。
- 性质测试只检查顺序,不检查元素守恒,可能放过重复、丢失或新增元素的实现。
- 直接把待测实现复制成参考实现,会让两边共享同一个缺陷;参考实现应来自独立算法或可信标准库。
本课练习
- 为二分查找编写示例、边界和随机差分测试。输入数组必须有序,并覆盖空数组、目标位于两端、目标不存在和重复值;验收条件是连续运行 1000 组固定种子随机数据均与线性查找结果一致。
- 人为把插入排序的循环条件改成
data[j] >= value,观察现有测试是否失败;再增加一个能够验证“稳定排序”的性质测试,验收条件是相同键值元素的原始相对顺序保持不变。
本课总结
- 示例与边界测试负责已知风险,随机差分测试负责扩大输入空间。
- 性质测试应验证多个独立不变量,避免只检查表面正确性。
- 固定随机种子和完整失败输入是定位、修复与回归验证的基础。
下一课预告
下一课将学习“基准测试与性能剖析”,把已经验证正确的算法放入公平、可重复的测量环境,并用性能数据定位真正的优化目标。
按自己的节奏,确认真正理解。