331 lines
12 KiB
C
331 lines
12 KiB
C
#include <c_MergeSort.h>
|
||
#include <stdlib.h>
|
||
|
||
/* ------------------------------------------------------------------------------------------------------------------ */
|
||
/* */
|
||
|
||
|
||
/**
|
||
* @brief 自顶向下归并排序核心合并内部函数（完全规避 c_size_t 下溢）
|
||
*
|
||
* 采用左闭右开区间映射，或精准的边界条件限制，确保所有的索引自加和自减都不触碰回绕风险。
|
||
*/
|
||
static void c_MergeInternal(char* array_base, c_size_t low, c_size_t mid, c_size_t high,
|
||
char* aux_buf, c_size_t size, c_SortCompare_t cmp, void* args)
|
||
{
|
||
// 将待合并的两个有序子区间 [low, mid] 和 [mid + 1, high] 的数据完整复制到辅助缓冲区
|
||
// 拷贝的总数据量为从 low 到 high（含）的闭区间元素总和
|
||
c_size_t total_elements = high - low + 1;
|
||
memcpy(aux_buf + (low * size), array_base + (low * size), total_elements * size);
|
||
|
||
c_size_t i = low; // 左半边子区间的游标起始点
|
||
c_size_t j = mid + 1; // 右半边子区间的游标起始点
|
||
|
||
// 双指针滑窗合并回原数组
|
||
for (c_size_t k = low; k <= high; k++) {
|
||
if (i > mid) {
|
||
// 左半边已经全部用尽，直接无脑拷贝右半边剩余元素
|
||
memcpy(array_base + (k * size), aux_buf + (j * size), size);
|
||
j++;
|
||
}
|
||
else if (j > high) {
|
||
// 右半边已经全部用尽，直接无脑拷贝左半边剩余元素
|
||
memcpy(array_base + (k * size), aux_buf + (i * size), size);
|
||
i++;
|
||
}
|
||
else {
|
||
// 核心双指针比对
|
||
char* elem_i = aux_buf + (i * size);
|
||
char* elem_j = aux_buf + (j * size);
|
||
|
||
// 使用 <= 0 判定。如果左边的值小于或等于右边，优先选用左边。
|
||
// 这正是归并排序能够完美保留相同元素原始先后相对位置（保持 Stable）的关键所在！
|
||
if (cmp(elem_i, elem_j, args) <= 0) {
|
||
memcpy(array_base + (k * size), elem_i, size);
|
||
i++;
|
||
} else {
|
||
memcpy(array_base + (k * size), elem_j, size);
|
||
j++;
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
/**
|
||
* @brief 递归驱动函数
|
||
*/
|
||
static void c_MergeSortRecursive(char* array_base, c_size_t low, c_size_t high,
|
||
char* aux_buf, c_size_t size, c_SortCompare_t cmp, void* args)
|
||
{
|
||
// 终止递归条件：当区间收缩到只包含 1 个元素时自然返回
|
||
if (low >= high) {
|
||
return;
|
||
}
|
||
|
||
// 防整数溢出的中间索引计算法
|
||
c_size_t mid = low + ((high - low) >> 1);
|
||
|
||
// 分治法阶段 1：左半区递归
|
||
c_MergeSortRecursive(array_base, low, mid, aux_buf, size, cmp, args);
|
||
|
||
// 分治法阶段 2：右半区递归（由于 mid + 1 永远大于 mid，不可能在此处发生无符号数反向绕回）
|
||
c_MergeSortRecursive(array_base, mid + 1, high, aux_buf, size, cmp, args);
|
||
|
||
// 分治法阶段 3：就地执行双向有序序列的高效合并
|
||
c_MergeInternal(array_base, low, mid, high, aux_buf, size, cmp, args);
|
||
}
|
||
|
||
/**
|
||
* @brief 工业级泛型自顶向下归并排序入口
|
||
*
|
||
* @param base 指向待排序连续数组首元素的指针
|
||
* @param num 数组中元素的总个数
|
||
* @param size 每个元素所占用的内存字节大小 (sizeof)
|
||
* @param cmp 带自定义上下文参数的比对回调函数指针 (不能为 NULL)
|
||
* @param args 传递给比对回调函数的自定义上下文参数指针
|
||
*/
|
||
void c_MergeSort(void* base, c_size_t num, c_size_t size, c_SortCompare_t cmp, void* args) {
|
||
if (!base || num < 2 || size == 0 || !cmp) {
|
||
return;
|
||
}
|
||
|
||
char* array_base = (char*)base;
|
||
|
||
// 归并排序无法实现真正的泛型就地常数级存储，必须在堆或外部开辟一块大小为 N 的临时辅助阴影缓冲区。
|
||
// 这里采用标准 malloc 动态分配。如果在嵌入式环境中，可以将其修改为用户传入或静态内存池分配。
|
||
char* aux_buf = (char*)malloc(num * size);
|
||
if (!aux_buf) {
|
||
return; // 分配失败防御
|
||
}
|
||
|
||
// 触发递归控制流：闭区间范围为 0 到 num - 1
|
||
// 由于 num >= 2，num - 1 经过了前置拦截，绝对不会引发 0 - 1 的无符号数最大值回绕灾难
|
||
c_MergeSortRecursive(array_base, 0, num - 1, aux_buf, size, cmp, args);
|
||
|
||
// 严密清理辅助缓冲区，斩断内存泄漏
|
||
free(aux_buf);
|
||
}
|
||
|
||
/* ------------------------------------------------------------------------------------------------------------------ */
|
||
/* */
|
||
|
||
/**
|
||
* @brief 内部辅助内联函数：获取两个无符号数中的较小值（防止宏重复计算）
|
||
*/
|
||
C_STATIC_FORCE_INLINE
|
||
c_size_t c_InternalMin(c_size_t a, c_size_t b) {
|
||
return (a < b) ? a : b;
|
||
}
|
||
|
||
/**
|
||
* @brief 归并排序核心合并内部函数（复用双指针滑窗逻辑）
|
||
*/
|
||
C_STATIC_FORCE_INLINE
|
||
void c_BU_MergeInternal(char* array_base, c_size_t low, c_size_t mid, c_size_t high,
|
||
char* aux_buf, c_size_t size, c_SortCompare_t cmp, void* args){
|
||
c_size_t total_elements = high - low + 1;
|
||
memcpy(aux_buf + (low * size), array_base + (low * size), total_elements * size);
|
||
|
||
c_size_t i = low;
|
||
c_size_t j = mid + 1;
|
||
|
||
for (c_size_t k = low; k <= high; k++) {
|
||
if (i > mid) {
|
||
memcpy(array_base + (k * size), aux_buf + (j * size), size);
|
||
j++;
|
||
}
|
||
else if (j > high) {
|
||
memcpy(array_base + (k * size), aux_buf + (i * size), size);
|
||
i++;
|
||
}
|
||
else {
|
||
char* elem_i = aux_buf + (i * size);
|
||
char* elem_j = aux_buf + (j * size);
|
||
|
||
if (cmp(elem_i, elem_j, args) <= 0) {
|
||
memcpy(array_base + (k * size), elem_i, size);
|
||
i++;
|
||
} else {
|
||
memcpy(array_base + (k * size), elem_j, size);
|
||
j++;
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
/**
|
||
* @brief 工业级泛型自底向上归并排序（纯迭代非递归，完全规避栈溢出风险）
|
||
*
|
||
* @param base 指向待排序连续数组首元素的指针
|
||
* @param num 数组中元素的总个数
|
||
* @param size 每个元素所占用的内存字节大小 (sizeof)
|
||
* @param cmp 带自定义上下文参数的比对回调函数指针 (不能为 NULL)
|
||
* @param args 传递给比对回调函数的自定义上下文参数指针
|
||
*/
|
||
void c_MergeSort_BottomUp(void* base, c_size_t num, c_size_t size, c_SortCompare_t cmp, void* args) {
|
||
if (!base || num < 2 || size == 0 || !cmp) {
|
||
return;
|
||
}
|
||
|
||
char* array_base = (char*)base;
|
||
|
||
// 分配 N 大小的临时阴影缓冲区
|
||
char* aux_buf = (char*)malloc(num * size);
|
||
if (!aux_buf) {
|
||
return;
|
||
}
|
||
|
||
// 外层循环：控制当前合并的子序列步长 sz (以 1, 2, 4, 8, ... 指数级翻倍递增)
|
||
// 限制条件：sz < num，由于通过前置校验限制 num >= 2，因此循环至少执行一轮
|
||
for (c_size_t sz = 1; sz < num; sz = sz + sz) {
|
||
|
||
// 内层循环：按当前子序列步长，成对进行两个子区间的有序合并
|
||
// 控制条件：low < num - sz。通过逆向加法或前置限制，确保 (num - sz) 不会发生无符号下溢
|
||
c_size_t limit = num - sz;
|
||
for (c_size_t low = 0; low < limit; low += sz + sz) {
|
||
|
||
// 计算当前左半边有序区间的终点 mid
|
||
c_size_t mid = low + sz - 1;
|
||
|
||
// 计算当前右半边有序区间的终点 high。
|
||
// 核心安全优化：若右半区不满足整步长大小，直接利用 c_InternalMin 将其安全截断到真实的最后一位 (num - 1)
|
||
// 由于通过前置校验，num - 1 绝对不会产生无符号回绕
|
||
c_size_t high = c_InternalMin(low + sz + sz - 1, num - 1);
|
||
|
||
// 就地执行数据合并
|
||
c_BU_MergeInternal(array_base, low, mid, high, aux_buf, size, cmp, args);
|
||
}
|
||
}
|
||
|
||
// 清理堆空间
|
||
free(aux_buf);
|
||
}
|
||
|
||
/* ------------------------------------------------------------------------------------------------------------------ */
|
||
/* */
|
||
|
||
// 设置小数组自适应截断阈值，通常在 12 - 16 之间性能达到极值
|
||
#define COMPONENT_MERGE_CUTOFF 15
|
||
|
||
/**
|
||
* @brief 局部内联优化的泛型插入排序（供归并排序降级使用，规避下溢风险）
|
||
*/
|
||
C_STATIC_FORCE_INLINE
|
||
void c_Internal_InsertionSort(char* base, c_size_t low, c_size_t high, c_size_t size, c_SortCompare_t cmp, void* args) {
|
||
for (c_size_t i = low + 1; i <= high; i++) {
|
||
c_size_t j = i;
|
||
char* item_i = base + (i * size);
|
||
|
||
// 栈上开辟单元素缓冲区，实现半交换单向平移优化
|
||
char v_buf[256];
|
||
memcpy(v_buf, item_i, size);
|
||
|
||
while (j > low) {
|
||
char* current = base + (j * size);
|
||
char* previous = base + ((j - 1) * size);
|
||
|
||
if (cmp(v_buf, previous, args) < 0) {
|
||
memcpy(current, previous, size);
|
||
j--;
|
||
} else {
|
||
break;
|
||
}
|
||
}
|
||
memcpy(base + (j * size), v_buf, size);
|
||
}
|
||
}
|
||
|
||
/**
|
||
* @brief 核心合并逻辑：直接从 src 合并到 dst，消除往返拷贝开销
|
||
*/
|
||
C_STATIC_FORCE_INLINE
|
||
void c_OptMergeInternal(char* src, char* dst, c_size_t low, c_size_t mid, c_size_t high,
|
||
c_size_t size, c_SortCompare_t cmp, void* args)
|
||
{
|
||
c_size_t i = low;
|
||
c_size_t j = mid + 1;
|
||
|
||
for (c_size_t k = low; k <= high; k++) {
|
||
if (i > mid) {
|
||
memcpy(dst + (k * size), src + (j * size), size);
|
||
j++;
|
||
}
|
||
else if (j > high) {
|
||
memcpy(dst + (k * size), src + (i * size), size);
|
||
i++;
|
||
}
|
||
else {
|
||
char* elem_i = src + (i * size);
|
||
char* elem_j = src + (j * size);
|
||
|
||
if (cmp(elem_i, elem_j, args) <= 0) {
|
||
memcpy(dst + (k * size), elem_i, size);
|
||
i++;
|
||
} else {
|
||
memcpy(dst + (k * size), elem_j, size);
|
||
j++;
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
/**
|
||
* @brief 优化版交替控制流递归核心
|
||
*
|
||
* 注意：这里的 src 和 dst 在每一层递归中都会发生调换，使得合并直接把数据推向正确的上一层载体。
|
||
*/
|
||
static void c_OptMergeRecursive(char* src, char* dst, c_size_t low, c_size_t high,
|
||
c_size_t size, c_SortCompare_t cmp, void* args)
|
||
{
|
||
// 优化点 1：小数组截断，当区间长度小于等于阈值时直接调用插入排序
|
||
if (high - low < COMPONENT_MERGE_CUTOFF) {
|
||
c_Internal_InsertionSort(dst, low, high, size, cmp, args);
|
||
return;
|
||
}
|
||
|
||
c_size_t mid = low + ((high - low) >> 1);
|
||
|
||
// 优化点 3：通过互换 src 与 dst 指针角色，使得子层计算出来的有序序列直接存储在 src 中
|
||
c_OptMergeRecursive(dst, src, low, mid, size, cmp, args);
|
||
c_OptMergeRecursive(dst, src, mid + 1, high, size, cmp, args);
|
||
|
||
// 优化点 2：有序性前置检查。
|
||
// 如果左半区间的最大元素已经小于或等于右半区的最小元素，说明当前整体已经完全有序
|
||
// 此时只需直接从 src 拷贝到 dst，完全免去滑窗合并在指令和缓存上的无效消耗
|
||
char* left_max = src + (mid * size);
|
||
char* right_min = src + ((mid + 1) * size);
|
||
if (cmp(left_max, right_min, args) <= 0) {
|
||
memcpy(dst + (low * size), src + (low * size), (high - low + 1) * size);
|
||
return;
|
||
}
|
||
|
||
// 正常合并：将两个子序列安全推入 dst 目标
|
||
c_OptMergeInternal(src, dst, low, mid, high, size, cmp, args);
|
||
}
|
||
|
||
/**
|
||
* @brief 工业级泛型优化版归并排序（哨兵阻断、小数组截断、零往返拷贝）
|
||
*/
|
||
void c_MergeSort_Optimized(void* base, c_size_t num, c_size_t size, c_SortCompare_t cmp, void* args) {
|
||
if (!base || num < 2 || size == 0 || !cmp) {
|
||
return;
|
||
}
|
||
|
||
char* array_base = (char*)base;
|
||
|
||
// 分配 N 大小的辅助阴影缓冲区
|
||
char* aux_buf = (char*)malloc(num * size);
|
||
if (!aux_buf) {
|
||
return;
|
||
}
|
||
|
||
// 初始化时将原始数据完整同步到辅助缓冲区中，以支持首次角色分调
|
||
memcpy(aux_buf, array_base, num * size);
|
||
|
||
// 触发安全递归：此时传入的两个缓冲区分别为 aux_buf 和 array_base。
|
||
// 最终排好序的元素会完美收拢落回到原数组 array_base 中。
|
||
c_OptMergeRecursive(aux_buf, array_base, 0, num - 1, size, cmp, args);
|
||
|
||
free(aux_buf);
|
||
}
|