34 lines
1.2 KiB
C
34 lines
1.2 KiB
C
|
#include <c_InsertionSort.h>
|
||
|
|
|
||
|
|
#include "c_Swap.h"
|
||
|
|
|
||
|
|
void c_InsertionSort(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;
|
||
|
|
|
||
|
|
// 外层循环：从第二个元素开始（无符号安全递增）
|
||
|
|
for (c_size_t i = 1; i < num; i++) {
|
||
|
|
c_size_t j = i;
|
||
|
|
|
||
|
|
// 内层循环：通过向前对比滑窗（j > 0）来规避无符号整数的下溢发生
|
||
|
|
while (j > 0) {
|
||
|
|
char* current = array_base + (j * size);
|
||
|
|
char* previous = array_base + ((j - 1) * size);
|
||
|
|
|
||
|
|
// 如果前一个元素大于当前元素，则说明顺序颠倒，需要向前执行数据挪动/交换
|
||
|
|
if (cmp(previous, current, args) > 0) {
|
||
|
|
// 泛型就地内存块交换 (In-place Swap)
|
||
|
|
c_Swap(previous, current, size);
|
||
|
|
j--;
|
||
|
|
} else {
|
||
|
|
// 已经到达正确的插入位置，直接阻断内层滑窗
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|