106 lines
4.5 KiB
C
106 lines
4.5 KiB
C
|
#include <c_HeapSort.h>
|
||
|
|
|
||
|
|
/**
|
||
|
|
* @brief 内部原子接口：泛型就地物理内存块高效率互换（复用项目基础组件思想）
|
||
|
|
*/
|
||
|
|
C_STATIC_FORCE_INLINE
|
||
|
|
void c_HS_InternalSwap(void* a, void* b, c_size_t size) {
|
||
|
|
if (a == b) return;
|
||
|
|
char* p1 = (char*)a;
|
||
|
|
char* p2 = (char*)b;
|
||
|
|
char temp_buf[256];
|
||
|
|
c_size_t bytes_left = size;
|
||
|
|
while (bytes_left > 0) {
|
||
|
|
c_size_t chunk = (bytes_left < sizeof(temp_buf)) ? bytes_left : sizeof(temp_buf);
|
||
|
|
memcpy(temp_buf, p1, chunk);
|
||
|
|
memcpy(p1, p2, chunk);
|
||
|
|
memcpy(p2, temp_buf, chunk);
|
||
|
|
p1 += chunk;
|
||
|
|
p2 += chunk;
|
||
|
|
bytes_left -= chunk;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
* @brief 堆排序核心下沉微调状态机（完全基于零基插槽的 c_size_t 安全加固）
|
||
|
|
*
|
||
|
|
* @param array_base 数组物理起始点
|
||
|
|
* @param parent 当前待下沉调整的父节点无符号物理下标位置
|
||
|
|
* @param num 当前有效堆数据边界（小于此边界的元素参与调整）
|
||
|
|
*/
|
||
|
|
static void c_HeapSort_SiftDown(char* array_base, c_size_t parent, c_size_t num, c_size_t size, c_SortCompare_t cmp, void* args) {
|
||
|
|
while (1) {
|
||
|
|
// 计算左子节点在零基插槽中的无符号索引：left = 2 * parent + 1
|
||
|
|
c_size_t left_child = (parent << 1) + 1;
|
||
|
|
|
||
|
|
// 🌟 前置上限拦截：若左子节点已经超越或等于当前堆边界，说明已到达叶子节点，物理隔绝后续加法溢出
|
||
|
|
if (left_child >= num) {
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
|
||
|
|
c_size_t larger_child = left_child;
|
||
|
|
c_size_t right_child = left_child + 1;
|
||
|
|
|
||
|
|
// 如果存在右子节点，且右子节点在您带 args 的自定义比对器中大于左子节点，则锁定右半区
|
||
|
|
if (right_child < num) {
|
||
|
|
char* p_left = array_base + (left_child * size);
|
||
|
|
char* p_right = array_base + (right_child * size);
|
||
|
|
if (cmp(p_right, p_left, args) > 0) {
|
||
|
|
larger_child = right_child;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
char* p_parent = array_base + (parent * size);
|
||
|
|
char* p_target = array_base + (larger_child * size);
|
||
|
|
|
||
|
|
// 如果最大子节点大于父节点，则执行泛型就地对调，并向下追踪迭代
|
||
|
|
if (cmp(p_target, p_parent, args) > 0) {
|
||
|
|
c_HS_InternalSwap(p_parent, p_target, size);
|
||
|
|
parent = larger_child;
|
||
|
|
} else {
|
||
|
|
break; // 局部大顶堆序完全达成，提前破出
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
* @brief 工业级泛型就地堆排序（Floyd 线性建堆 + 常数级空间控制）
|
||
|
|
*
|
||
|
|
* @param base 指向待排序连续数组首元素的指针
|
||
|
|
* @param num 数组中元素的总个数
|
||
|
|
* @param size 每个元素所占用的内存字节大小 (sizeof)
|
||
|
|
* @param cmp 带自定义上下文参数的比对回调函数指针 (不能为 NULL)
|
||
|
|
* @param args 传递给比对回调函数的自定义上下文参数指针
|
||
|
|
*/
|
||
|
|
void c_HeapSort(void* base, c_size_t num, c_size_t size, c_SortCompare_t cmp, void* args) {
|
||
|
|
// 边界与防御性校验：元素少于 2 个或参数非法时无需排序
|
||
|
|
if (!base || num < 2 || size == 0 || !cmp) {
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
|
||
|
|
char* array_base = (char*)base;
|
||
|
|
|
||
|
|
// =================================================================
|
||
|
|
// 阶段 1：Floyd 自底向上线性建堆（Heapify，时间复杂度为完美的 O(N)）
|
||
|
|
// 从最后一个非叶子节点开始倒序执行下沉。最后一个非叶子节点无符号下标为 (num / 2) - 1
|
||
|
|
// 为了防止 (num / 2) - 1 在极端时引发下溢，我们采用无符号安全的向前递减边界拦截法
|
||
|
|
// =================================================================
|
||
|
|
c_size_t i = num >> 1;
|
||
|
|
while (i > 0) {
|
||
|
|
i--; // 此时 i 从 (num/2)-1 平滑递减到 0，彻底封死下溢到最大无符号数的苗头
|
||
|
|
c_HeapSort_SiftDown(array_base, i, num, size, cmp, args);
|
||
|
|
}
|
||
|
|
|
||
|
|
// =================================================================
|
||
|
|
// 阶段 2：迭代销毁堆并就地重排（时间复杂度 O(N log N)）
|
||
|
|
// 每次将大顶堆的堆顶（最大值）同当前的有效堆尾元素对调，随后缩小堆边界并下沉堆顶
|
||
|
|
// =================================================================
|
||
|
|
for (c_size_t j = num - 1; j > 0; j--) {
|
||
|
|
// 交换当前最大的堆顶 array_base[0] 到合法的排序落脚点 array_base[j] 处
|
||
|
|
c_HS_InternalSwap(array_base, array_base + (j * size), size);
|
||
|
|
|
||
|
|
// 重新对缩小后的有效堆域区间 [0, j-1] 执行自适应堆顶下沉重建
|
||
|
|
c_HeapSort_SiftDown(array_base, 0, j, size, cmp, args);
|
||
|
|
}
|
||
|
|
}
|