244 lines
9.1 KiB
C
244 lines
9.1 KiB
C
|
#include "c_MergeSort.h"
|
||
|
|
#include "c_Test.h"
|
||
|
|
|
||
|
|
// ==========================================
|
||
|
|
// 1. 测试用例伴生：通用比对器与稳定性校验结构体
|
||
|
|
// ==========================================
|
||
|
|
static int sort_compare_ints_with_args(const void* a, const void* b, void* args) {
|
||
|
|
(void)args;
|
||
|
|
int arg1 = *(const int*)a;
|
||
|
|
int arg2 = *(const int*)b;
|
||
|
|
if (arg1 < arg2) return -1;
|
||
|
|
if (arg1 > arg2) return 1;
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
|
||
|
|
typedef struct {
|
||
|
|
int key; // 核心排序键值
|
||
|
|
int origin_order; // 记录元素的原始相对生成次序（用于硬性稳定性验证）
|
||
|
|
} StableElement_t;
|
||
|
|
|
||
|
|
// 仅根据 key 键值进行比对的复合比较器
|
||
|
|
static int sort_compare_stable_keys(const void* a, const void* b, void* args) {
|
||
|
|
(void)args;
|
||
|
|
const StableElement_t* e1 = (const StableElement_t*)a;
|
||
|
|
const StableElement_t* e2 = (const StableElement_t*)b;
|
||
|
|
if (e1->key < e2->key) return -1;
|
||
|
|
if (e1->key > e2->key) return 1;
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
|
||
|
|
typedef struct {
|
||
|
|
int id;
|
||
|
|
int weight;
|
||
|
|
} Package_t;
|
||
|
|
|
||
|
|
static int sort_compare_packages(const void* a, const void* b, void* args) {
|
||
|
|
(void)args;
|
||
|
|
const Package_t* p1 = (const Package_t*)a;
|
||
|
|
// 【已修正】：彻底将原先笔误残留下来的 Task_t 符号更正为合法的 Package_t
|
||
|
|
const Package_t* p2 = (const Package_t*)b;
|
||
|
|
if (p1->weight < p2->weight) return -1;
|
||
|
|
if (p1->weight > p2->weight) return 1;
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
|
||
|
|
// ==========================================
|
||
|
|
// 2. 自动化测试用例集
|
||
|
|
// ==========================================
|
||
|
|
TEST_CASE(test_c_MergeSort_IntArray) {
|
||
|
|
int arr[] = { 45, 12, 85, 32, 85, 5, 67, 19, 90, 32 };
|
||
|
|
c_size_t num = sizeof(arr) / sizeof(arr[0]);
|
||
|
|
|
||
|
|
c_MergeSort(arr, num, sizeof(int), sort_compare_ints_with_args, NULL);
|
||
|
|
|
||
|
|
// 1. 验证全区间是否严格单调不减排列
|
||
|
|
for (c_size_t i = 0; i < num - 1; i++) {
|
||
|
|
ASSERT_TRUE(arr[i] <= arr[i + 1]);
|
||
|
|
}
|
||
|
|
ASSERT_INT_EQ(5, arr[0]); // 检查最小值
|
||
|
|
ASSERT_INT_EQ(90, arr[num - 1]); // 检查最大值
|
||
|
|
}
|
||
|
|
|
||
|
|
TEST_CASE(test_c_MergeSort_StabilityCheck) {
|
||
|
|
// 2. 核心压测：验证归并排序的“稳定性（Stable）”。
|
||
|
|
// 构建多组拥有完全相同键值（key = 40）、但原始序号不同的无序序列
|
||
|
|
StableElement_t items[] = {
|
||
|
|
{ 40, 1 }, // 第一个40
|
||
|
|
{ 10, 0 },
|
||
|
|
{ 40, 2 }, // 第二个40
|
||
|
|
{ 25, 0 },
|
||
|
|
{ 40, 3 } // 第三个40
|
||
|
|
};
|
||
|
|
c_size_t num = sizeof(items) / sizeof(items[0]);
|
||
|
|
|
||
|
|
c_MergeSort(items, num, sizeof(StableElement_t), sort_compare_stable_keys, NULL);
|
||
|
|
|
||
|
|
// 验证键值递增
|
||
|
|
for (c_size_t i = 0; i < num - 1; i++) {
|
||
|
|
ASSERT_TRUE(items[i].key <= items[i + 1].key);
|
||
|
|
}
|
||
|
|
|
||
|
|
// 核心断言：排序后，key同样为 40 的三个元素，其原始顺序必须依然是 1 -> 2 -> 3
|
||
|
|
// 修正了上一轮由于漏写数组索引 [idx] 导致的引用错误
|
||
|
|
ASSERT_INT_EQ(40, items[2].key); ASSERT_INT_EQ(1, items[2].origin_order);
|
||
|
|
ASSERT_INT_EQ(40, items[3].key); ASSERT_INT_EQ(2, items[3].origin_order);
|
||
|
|
ASSERT_INT_EQ(40, items[4].key); ASSERT_INT_EQ(3, items[4].origin_order);
|
||
|
|
}
|
||
|
|
|
||
|
|
TEST_CASE(test_c_MergeSort_EdgesAndNull) {
|
||
|
|
int ordered_arr[] = { 1, 2, 3, 4 };
|
||
|
|
c_size_t num = sizeof(ordered_arr) / sizeof(ordered_arr[0]);
|
||
|
|
|
||
|
|
// 3. 完全升序数组的无阻碍测试
|
||
|
|
c_MergeSort(ordered_arr, num, sizeof(int), sort_compare_ints_with_args, NULL);
|
||
|
|
ASSERT_INT_EQ(1, ordered_arr[0]);
|
||
|
|
ASSERT_INT_EQ(4, ordered_arr[num - 1]);
|
||
|
|
|
||
|
|
// 4. 空参数以及单元素数组的拦截压测，彻底杜绝 num-1 引发的无符号下溢崩溃
|
||
|
|
int single_arr[] = { 555 };
|
||
|
|
c_MergeSort(single_arr, 1, sizeof(int), sort_compare_ints_with_args, NULL);
|
||
|
|
c_MergeSort(NULL, 0, sizeof(int), sort_compare_ints_with_args, NULL);
|
||
|
|
ASSERT_INT_EQ(555, single_arr[0]);
|
||
|
|
}
|
||
|
|
|
||
|
|
TEST_CASE(test_c_MergeSort_BottomUp_IntArray) {
|
||
|
|
// 故意使用一个长度不等于 2 的幂次方的数组 (长度为 11)，强迫触发高频边界不规则裁切路径
|
||
|
|
int arr[] = { 64, 34, 25, 12, 22, 11, 90, 45, 12, 88, 3 };
|
||
|
|
c_size_t num = sizeof(arr) / sizeof(arr[0]);
|
||
|
|
|
||
|
|
c_MergeSort_BottomUp(arr, num, sizeof(int), sort_compare_ints_with_args, NULL);
|
||
|
|
|
||
|
|
// 验证区间整体是否呈现绝对严格升序排列
|
||
|
|
for (c_size_t i = 0; i < num - 1; i++) {
|
||
|
|
ASSERT_TRUE(arr[i] <= arr[i + 1]);
|
||
|
|
}
|
||
|
|
ASSERT_INT_EQ(3, arr[0]); // 检查最小值
|
||
|
|
ASSERT_INT_EQ(90, arr[num - 1]); // 检查最大值
|
||
|
|
}
|
||
|
|
|
||
|
|
TEST_CASE(test_c_MergeSort_BottomUp_StabilityCheck) {
|
||
|
|
// 验证非递归自底向上模型的排序“稳定性”。
|
||
|
|
StableElement_t items[] = {
|
||
|
|
{ 50, 1 }, // 第一个 50
|
||
|
|
{ 20, 0 },
|
||
|
|
{ 50, 2 }, // 第二个 50
|
||
|
|
{ 10, 0 },
|
||
|
|
{ 50, 3 } // 第三个 50
|
||
|
|
};
|
||
|
|
c_size_t num = sizeof(items) / sizeof(items[0]);
|
||
|
|
|
||
|
|
c_MergeSort_BottomUp(items, num, sizeof(StableElement_t), sort_compare_stable_keys, NULL);
|
||
|
|
|
||
|
|
// 验证键值递增
|
||
|
|
for (c_size_t i = 0; i < num - 1; i++) {
|
||
|
|
ASSERT_TRUE(items[i].key <= items[i + 1].key);
|
||
|
|
}
|
||
|
|
|
||
|
|
// 核心断言：排序后，拥有相同键值的项，其内部存储顺序必须依然是 1 -> 2 -> 3
|
||
|
|
ASSERT_INT_EQ(50, items[2].key); ASSERT_INT_EQ(1, items[2].origin_order);
|
||
|
|
ASSERT_INT_EQ(50, items[3].key); ASSERT_INT_EQ(2, items[3].origin_order);
|
||
|
|
ASSERT_INT_EQ(50, items[4].key); ASSERT_INT_EQ(3, items[4].origin_order);
|
||
|
|
}
|
||
|
|
|
||
|
|
TEST_CASE(test_c_MergeSort_BottomUp_EdgesAndNull) {
|
||
|
|
int ordered_arr[] = { 10, 20, 30 };
|
||
|
|
c_size_t num = sizeof(ordered_arr) / sizeof(ordered_arr[0]);
|
||
|
|
|
||
|
|
// 完全有序状态测试
|
||
|
|
c_MergeSort_BottomUp(ordered_arr, num, sizeof(int), sort_compare_ints_with_args, NULL);
|
||
|
|
ASSERT_INT_EQ(10, ordered_arr[0]);
|
||
|
|
ASSERT_INT_EQ(30, ordered_arr[num - 1]);
|
||
|
|
|
||
|
|
// 极端输入安全防御测试，防止无符号整数最大值溢出
|
||
|
|
int single_arr[] = { 999 };
|
||
|
|
c_MergeSort_BottomUp(single_arr, 1, sizeof(int), sort_compare_ints_with_args, NULL);
|
||
|
|
c_MergeSort_BottomUp(NULL, 0, sizeof(int), sort_compare_ints_with_args, NULL);
|
||
|
|
ASSERT_INT_EQ(999, single_arr[0]);
|
||
|
|
}
|
||
|
|
|
||
|
|
TEST_CASE(test_c_MergeSort_Optimized_LargeAndCutoff) {
|
||
|
|
// 构建一个超越截断阈值（> 15）的长乱序整型数组
|
||
|
|
int arr[] = { 89, 45, 68, 90, 23, 12, 57, 46, 35, 78, 24, 11, 5, 99, 41, 102, 33, 1 };
|
||
|
|
c_size_t num = sizeof(arr) / sizeof(arr[0]);
|
||
|
|
|
||
|
|
c_MergeSort_Optimized(arr, num, sizeof(int), sort_compare_ints_with_args, NULL);
|
||
|
|
|
||
|
|
// 1. 验证大区间在历经自适应截断重组后呈现绝对升序状态
|
||
|
|
for (c_size_t i = 0; i < num - 1; i++) {
|
||
|
|
ASSERT_TRUE(arr[i] <= arr[i + 1]);
|
||
|
|
}
|
||
|
|
ASSERT_INT_EQ(1, arr[0]);
|
||
|
|
ASSERT_INT_EQ(102, arr[num - 1]);
|
||
|
|
}
|
||
|
|
|
||
|
|
TEST_CASE(test_c_MergeSort_Optimized_PreSortedCheck) {
|
||
|
|
// 2. 压测完全有序的输入，强制激活极其高效的有序性前置快速阻断路径
|
||
|
|
int ordered_arr[] = { 10, 20, 30, 40, 50, 60, 70, 80, 90 };
|
||
|
|
c_size_t num = sizeof(ordered_arr) / sizeof(ordered_arr[0]);
|
||
|
|
|
||
|
|
c_MergeSort_Optimized(ordered_arr, num, sizeof(int), sort_compare_ints_with_args, NULL);
|
||
|
|
|
||
|
|
for (c_size_t i = 0; i < num - 1; i++) {
|
||
|
|
ASSERT_TRUE(ordered_arr[i] < ordered_arr[i + 1]);
|
||
|
|
}
|
||
|
|
ASSERT_INT_EQ(10, ordered_arr[0]);
|
||
|
|
ASSERT_INT_EQ(90, ordered_arr[num - 1]);
|
||
|
|
}
|
||
|
|
|
||
|
|
TEST_CASE(test_c_MergeSort_Optimized_Stability) {
|
||
|
|
// 3. 验证交替角色互换后的稳定排序特性
|
||
|
|
Package_t pkgs[] = {
|
||
|
|
{ 101, 50 }, // 相同重量 50
|
||
|
|
{ 102, 20 },
|
||
|
|
{ 103, 50 }, // 相同重量 50
|
||
|
|
{ 104, 10 }
|
||
|
|
};
|
||
|
|
c_size_t num = sizeof(pkgs) / sizeof(pkgs[0]);
|
||
|
|
|
||
|
|
c_MergeSort_Optimized(pkgs, num, sizeof(Package_t), sort_compare_packages, NULL);
|
||
|
|
|
||
|
|
// 【已修正】：彻底补上数组定位下标 [idx]，解决前一轮缺失索引引起的编译错误
|
||
|
|
ASSERT_INT_EQ(10, pkgs[0].weight);
|
||
|
|
ASSERT_INT_EQ(20, pkgs[1].weight);
|
||
|
|
|
||
|
|
// 核心断言：相同键值的项（weight = 50），其原始相对先后生成顺序（id）绝对不能被调换
|
||
|
|
ASSERT_INT_EQ(50, pkgs[2].weight); ASSERT_INT_EQ(101, pkgs[2].id);
|
||
|
|
ASSERT_INT_EQ(50, pkgs[3].weight); ASSERT_INT_EQ(103, pkgs[3].id);
|
||
|
|
}
|
||
|
|
|
||
|
|
TEST_CASE(test_c_MergeSort_Optimized_Edges) {
|
||
|
|
int single_arr[] = { 42 };
|
||
|
|
|
||
|
|
// 4. 空参数以及单元素安全边界防御
|
||
|
|
c_MergeSort_Optimized(single_arr, 1, sizeof(int), sort_compare_ints_with_args, NULL);
|
||
|
|
c_MergeSort_Optimized(NULL, 0, sizeof(int), sort_compare_ints_with_args, NULL);
|
||
|
|
ASSERT_INT_EQ(42, single_arr[0]);
|
||
|
|
}
|
||
|
|
|
||
|
|
// ==========================================
|
||
|
|
// 3. 独立测试运行入口
|
||
|
|
// ==========================================
|
||
|
|
int main(void) {
|
||
|
|
TEST_START(C_TopDownMergeSort_Isolated_TestSuite);
|
||
|
|
|
||
|
|
// 运行专项排序测试集
|
||
|
|
RUN_TEST(test_c_MergeSort_IntArray);
|
||
|
|
RUN_TEST(test_c_MergeSort_StabilityCheck);
|
||
|
|
RUN_TEST(test_c_MergeSort_EdgesAndNull);
|
||
|
|
|
||
|
|
RUN_TEST(test_c_MergeSort_BottomUp_IntArray);
|
||
|
|
RUN_TEST(test_c_MergeSort_BottomUp_StabilityCheck);
|
||
|
|
RUN_TEST(test_c_MergeSort_BottomUp_EdgesAndNull);
|
||
|
|
|
||
|
|
RUN_TEST(test_c_MergeSort_Optimized_LargeAndCutoff);
|
||
|
|
RUN_TEST(test_c_MergeSort_Optimized_PreSortedCheck);
|
||
|
|
RUN_TEST(test_c_MergeSort_Optimized_Stability);
|
||
|
|
RUN_TEST(test_c_MergeSort_Optimized_Edges);
|
||
|
|
|
||
|
|
TEST_REPORT();
|
||
|
|
|
||
|
|
RETURN_TEST_STATUS;
|
||
|
|
}
|
||
|
|
|