76 lines
3.2 KiB
C
76 lines
3.2 KiB
C
|
#include <c_InsertionSortX.h>
|
||
|
|
#include <c_Swap.h>
|
||
|
|
|
||
|
|
void c_InsertionSortX(void* array, c_size_t array_size, c_size_t item_size, c_SortCompare_t cmp, void* args) {
|
||
|
|
// 边界与防御性校验：元素少于 2 个或参数非法时无需排序
|
||
|
|
if (!array || array_size < 2 || item_size == 0 || !cmp) {
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
|
||
|
|
char* array_base = (char*)array;
|
||
|
|
|
||
|
|
// 栈上开辟 256 字节的局部单元素缓冲区，用于半交换中暂存临时变量 v
|
||
|
|
// 这避免了 malloc 带来的堆内存分配，同时保证线程安全
|
||
|
|
char v_buf[item_size];
|
||
|
|
|
||
|
|
// =================================================================
|
||
|
|
// 阶段 1：倒序滑窗，寻找绝对最小值推至首位（充当左边界哨兵）
|
||
|
|
// 为了彻底杜绝无符号整数自减至 0 导致的下溢（Underflow），此处采用向前平移法
|
||
|
|
// =================================================================
|
||
|
|
c_size_t exchanges = 0;
|
||
|
|
for (c_size_t i = array_size; i > 1; i--) {
|
||
|
|
const c_size_t current_idx = i - 1;
|
||
|
|
char* current = array_base + (current_idx * item_size);
|
||
|
|
char* previous = array_base + ((current_idx - 1) * item_size);
|
||
|
|
|
||
|
|
// 如果后面的元素比前面小，执行泛型交换（复用您的 c_Swap 思想）
|
||
|
|
if (cmp(current, previous, args) < 0) {
|
||
|
|
c_Swap(current, previous, item_size);
|
||
|
|
exchanges++;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// 统计学优化：如果第一轮扫描发现本来就是绝对递增的（exchanges == 0），说明完全有序，直接退出
|
||
|
|
if (exchanges == 0) {
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
|
||
|
|
// =================================================================
|
||
|
|
// 阶段 2：带有半交换（单向平移）的插入排序核心
|
||
|
|
// 由于阶段 1 已经把全局最小值放到了 array_base[0]，后续天然具备了边界防护
|
||
|
|
// =================================================================
|
||
|
|
for (c_size_t i = 2; i < array_size; i++) {
|
||
|
|
const char* item_i = array_base + (i * item_size);
|
||
|
|
|
||
|
|
// 暂存当前需要插入的元素：v = a[i]
|
||
|
|
memcpy(v_buf, item_i, item_size);
|
||
|
|
|
||
|
|
c_size_t j = i;
|
||
|
|
while (1) {
|
||
|
|
// 哨兵边界强御：因为 j 是无符号数，在此处增加前置保护
|
||
|
|
// 实际上由于 array_base[0] 是最小值，理论上 cmp(v, previous) 永远不可能在 j==1 时成立
|
||
|
|
// 但为了防御恶意外部比对器损坏，加入 j > 0 联锁，确保绝不发生无符号下溢
|
||
|
|
if (j == 0) {
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
|
||
|
|
char* current = array_base + (j * item_size);
|
||
|
|
char* previous = array_base + ((j - 1) * item_size);
|
||
|
|
|
||
|
|
// 比较暂存的 v 和前一个元素 previous。如果 v 更小，说明前面的元素需要后移
|
||
|
|
if (cmp(v_buf, previous, args) < 0) {
|
||
|
|
// 半交换核心：单向覆盖 a[j] = a[j-1]
|
||
|
|
memcpy(current, previous, item_size);
|
||
|
|
j--;
|
||
|
|
} else {
|
||
|
|
// 顺序正确，找到了插入位置，直接退出平移滑窗
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// 将暂存的元素写入最终位置：a[j] = v
|
||
|
|
char* item_j = array_base + (j * item_size);
|
||
|
|
memcpy(item_j, v_buf, item_size);
|
||
|
|
}
|
||
|
|
}
|