56 lines
2.0 KiB
C
56 lines
2.0 KiB
C
#include <c_ShellSort.h>
|
|
|
|
|
|
void c_ShellSort(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;
|
|
|
|
// 栈上开辟 256 字节单元素临时变量缓冲区，支持半交换平移，降低物理拷贝开销
|
|
char v_buf[size];
|
|
|
|
// 1. 计算 Knuth 递增步长序列的最大安全上界 (1, 4, 13, 40, 121, ...)
|
|
// 步长必须严格小于 num，使用除法逆向校验，彻底防止 (3 * gap + 1) 无符号算术溢出
|
|
c_size_t gap = 1;
|
|
while (gap <= (num - 1) / 3) {
|
|
gap = 3 * gap + 1;
|
|
}
|
|
|
|
// 2. 核心跨步长交替排序状态机
|
|
while (gap > 0) {
|
|
// 外层插入排序轮次：从无符号下标 gap 开始单调递增
|
|
for (c_size_t i = gap; i < num; i++) {
|
|
char* item_i = array_base + (i * size);
|
|
|
|
// 暂存当前待排元素：v = a[i]
|
|
memcpy(v_buf, item_i, size);
|
|
|
|
c_size_t j = i;
|
|
|
|
// 内层跨步长平移循环：严格控制 j >= gap，阻止无符号减法 (j - gap) 发生下溢回绕
|
|
while (j >= gap) {
|
|
char* current = array_base + (j * size);
|
|
char* previous = array_base + ((j - gap) * size);
|
|
|
|
// 如果暂存的 v_buf 小于前驱跨步长元素 previous，则前驱元素单向后移覆盖
|
|
if (cmp(v_buf, previous, args) < 0) {
|
|
memcpy(current, previous, size); // a[j] = a[j-gap]
|
|
j -= gap; // 安全步进自减
|
|
} else {
|
|
break; // 归位完成，阻断内层循环
|
|
}
|
|
}
|
|
|
|
// 将暂存数据写回最终安全插槽：a[j] = v
|
|
char* item_target = array_base + (j * size);
|
|
memcpy(item_target, v_buf, size);
|
|
}
|
|
|
|
// 步长衰减
|
|
gap /= 3;
|
|
}
|
|
}
|