480 lines
18 KiB
C
480 lines
18 KiB
C
#include <c_QuickSort.h>
|
||
|
||
/* ------------------------------------------------------------------------------------------------------------------ */
|
||
/* */
|
||
|
||
#include <string.h>
|
||
|
||
|
||
/**
|
||
* @brief 原子操作：泛型就地物理内存块交换
|
||
*/
|
||
/**
|
||
* @brief 彻底加固的泛型物理内存块互换接口（256字节自适应滑窗，绝不踩踏）
|
||
*/
|
||
C_STATIC_FORCE_INLINE
|
||
void c_QS_Swap(void* a, void* b, c_size_t size) {
|
||
if (a == b || size == 0) 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 最直观的 Lomuto 单路划分递归核心（完全规避 c_size_t 下溢）
|
||
*/
|
||
static void c_QuickSortRecursive(char* array_base, c_size_t low, c_size_t high, c_size_t size, c_SortCompare_t cmp, void* args) {
|
||
// 递归终止：区间无元素或仅剩 1 个元素时安全返回
|
||
if (low >= high) {
|
||
return;
|
||
}
|
||
|
||
// 1. Lomuto 划分核心：选取当前区间的最后一个元素作为基准点 (Pivot)
|
||
char* pivot = array_base + (high * size);
|
||
|
||
// i 记录的是“小于基准点的元素”的右边界
|
||
c_size_t i = low;
|
||
|
||
// j 游标从 low 开始单调递增扫描到 high - 1
|
||
for (c_size_t j = low; j < high; j++) {
|
||
// 如果当前元素比基准点小，就把她跟 i 位置的数据互换，并将 i 向右推一步
|
||
if (cmp(array_base + (j * size), pivot, args) < 0) {
|
||
c_QS_Swap(array_base + (i * size), array_base + (j * size), size);
|
||
i++;
|
||
}
|
||
}
|
||
|
||
// 最后，将处于 high 位置的基准点本身，交换到边界 i 的地方归位
|
||
c_QS_Swap(array_base + (i * size), pivot, size);
|
||
|
||
// 此时绝对位置 i 处的元素已经各就各位。接下来两侧递归分治：
|
||
// 左半区：[low, i-1] | 右半区：[i+1, high]
|
||
|
||
// 核心安全防护：只有 i > 0 且 i - 1 > low 时才执行左半区减法，彻底封死无符号下溢
|
||
if (i > 0 && (i - 1) > low) {
|
||
c_QuickSortRecursive(array_base, low, i - 1, size, cmp, args);
|
||
}
|
||
|
||
// 只有 i + 1 < high 时才执行右半区加法，防止整数溢出
|
||
if (i < high) {
|
||
c_QuickSortRecursive(array_base, i + 1, high, size, cmp, args);
|
||
}
|
||
}
|
||
|
||
/**
|
||
* @brief 迭代版本泛型快速排序标准入口
|
||
*/
|
||
void c_QuickSort_Recursive(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;
|
||
|
||
// 闭区间从 0 开始到 num - 1。经过前置 num >= 2 的拦截，num - 1 绝对不会下溢
|
||
c_QuickSortRecursive(array_base, 0, num - 1, size, cmp, args);
|
||
}
|
||
|
||
/* ------------------------------------------------------------------------------------------------------------------ */
|
||
/* */
|
||
|
||
|
||
|
||
/**
|
||
* @brief Dijkstra 三路划分标准安全控制流
|
||
*/
|
||
static void c_QuickSort3WayRecursive(char* array_base, c_size_t low, c_size_t high, c_size_t size, c_SortCompare_t cmp, void* args) {
|
||
if (low >= high) {
|
||
return;
|
||
}
|
||
|
||
// 🌟【终极加固核心】：在局部栈上开辟只读缓冲区，将原始枢轴的内容完整镜像拷贝出来！
|
||
// 256字节支持绝大多数基础数据类型与中小型业务结构体
|
||
char pivot_buf[size];
|
||
memcpy(pivot_buf, array_base + (low * size), size);
|
||
|
||
c_size_t lt = low; // lt 维护小于 pivot 区间的右边界
|
||
c_size_t i = low + 1; // i 为当前单调递增扫描指针
|
||
c_size_t gt = high; // gt 维护大于 pivot 区间的左边界
|
||
|
||
while (i <= gt) {
|
||
char* item_i = array_base + (i * size);
|
||
|
||
// 🌟【核心修正】：后续所有的比对，全部投喂只读的临时影子副本 pivot_buf，
|
||
// 彻底绝缘由于首位数据被物理 Swap 覆盖导致的基准值污染！
|
||
int cmp_res = cmp(item_i, pivot_buf, args);
|
||
|
||
if (cmp_res < 0) {
|
||
c_QS_Swap(array_base + (lt * size), item_i, size);
|
||
lt++;
|
||
i++;
|
||
}
|
||
else if (cmp_res > 0) {
|
||
c_QS_Swap(item_i, array_base + (gt * size), size);
|
||
if (gt == i) {
|
||
break;
|
||
}
|
||
gt--;
|
||
}
|
||
else {
|
||
i++;
|
||
}
|
||
}
|
||
|
||
// -----------------------------------------------------------------
|
||
// 纯单调递增分治：隔离无符号整数下溢
|
||
// -----------------------------------------------------------------
|
||
if (lt > low) {
|
||
c_size_t left_high = lt - 1;
|
||
if (low < left_high) {
|
||
c_QuickSort3WayRecursive(array_base, low, left_high, size, cmp, args);
|
||
}
|
||
}
|
||
|
||
if (gt < high) {
|
||
c_QuickSort3WayRecursive(array_base, gt + 1, high, size, cmp, args);
|
||
}
|
||
}
|
||
|
||
/**
|
||
* @brief 对外标准标准入口
|
||
*/
|
||
void c_QuickSort_3Way(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;
|
||
c_QuickSort3WayRecursive(array_base, 0, num - 1, size, cmp, args);
|
||
}
|
||
|
||
/* ------------------------------------------------------------------------------------------------------------------ */
|
||
/* */
|
||
|
||
#define COMPONENT_QS_CUTOFF 15
|
||
|
||
/**
|
||
* @brief 局部内联优化的泛型插入排序（供快排小区间降级调用）
|
||
*/
|
||
static void c_OptQS_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 三数取中（Median-of-Three）预处理逻辑
|
||
*
|
||
* 对首、中、尾三处元素进行就地排序，并将中位数物理挪动到区间最左侧（low 位置）充当主轴
|
||
*/
|
||
static void c_OptQS_MedianOfThree(char* base, c_size_t low, c_size_t high, c_size_t size, c_SortCompare_t cmp, void* args) {
|
||
c_size_t mid = low + ((high - low) >> 1);
|
||
char* E_low = base + (low * size);
|
||
char* E_mid = base + (mid * size);
|
||
char* E_high = base + (high * size);
|
||
|
||
if (cmp(E_mid, E_low, args) < 0) c_QS_Swap(E_mid, E_low, size);
|
||
if (cmp(E_high, E_low, args) < 0) c_QS_Swap(E_high, E_low, size);
|
||
if (cmp(E_mid, E_high, args) < 0) c_QS_Swap(E_mid, E_high, size);
|
||
|
||
// 此时首尾中三点已升序，将作为中位数的 E_high 与 E_low 交换，确保枢轴位于起点
|
||
c_QS_Swap(E_low, E_high, size);
|
||
}
|
||
|
||
/**
|
||
* @brief 经典 Hoare 双路划分与递归核心（纯加法单调驱动，规避下溢）
|
||
*/
|
||
static void c_OptQuickSortRecursive(char* array_base, c_size_t low, c_size_t high, c_size_t size, c_SortCompare_t cmp, void* args) {
|
||
// 优化点 1：小数组自适应截断降级
|
||
if (high - low < COMPONENT_QS_CUTOFF) {
|
||
c_OptQS_InsertionSort(array_base, low, high, size, cmp, args);
|
||
return;
|
||
}
|
||
|
||
// 优化点 2：激活三数取中，粉碎倒序或已排序序列的退化隐患
|
||
c_OptQS_MedianOfThree(array_base, low, high, size, cmp, args);
|
||
|
||
// 🌟 影子副本加固：将选取出的中位数枢轴数据复制到只读栈空间，绝缘交换别名污染！
|
||
char pivot_buf[size];
|
||
memcpy(pivot_buf, array_base + (low * size), size);
|
||
|
||
// Hoare 划分指针双向逼近控制
|
||
c_size_t i = low;
|
||
c_size_t j = high + 1; // 开区间初始边界
|
||
|
||
while (1) {
|
||
// 左指针 i 向右单调逼近，直到遇到大于或等于枢轴的元素才停止
|
||
do {
|
||
i++;
|
||
} while (i <= high && cmp(array_base + (i * size), pivot_buf, args) < 0);
|
||
|
||
// 右指针 j 向左单调收缩，直到遇到小于或等于枢轴的元素才停止
|
||
do {
|
||
j--;
|
||
} while (j >= low && cmp(array_base + (j * size), pivot_buf, args) > 0);
|
||
|
||
// 如果双向指针交叉，说明本次划分区域完全合拢
|
||
if (i >= j) {
|
||
break;
|
||
}
|
||
|
||
// 强行物理对调 i 和 j 处的元素（把大数顶到右边，小数挪到左边）
|
||
c_QS_Swap(array_base + (i * size), array_base + (j * size), size);
|
||
}
|
||
|
||
// 将驻留在 low 位置的枢轴元素与分界点 j 的元素进行对调归位
|
||
c_QS_Swap(array_base + (low * size), array_base + (j * size), size);
|
||
|
||
// -----------------------------------------------------------------
|
||
// 优化点 3：纯加法约束的分治控制，阻断无符号整数减法下溢
|
||
// -----------------------------------------------------------------
|
||
if (j > low) {
|
||
c_size_t left_high = j - 1;
|
||
if (low < left_high) {
|
||
c_OptQuickSortRecursive(array_base, low, left_high, size, cmp, args);
|
||
}
|
||
}
|
||
|
||
if (j < high) {
|
||
c_OptQuickSortRecursive(array_base, j + 1, high, size, cmp, args);
|
||
}
|
||
}
|
||
|
||
/**
|
||
* @brief 工业级三层优化双路快速排序标准对外入口
|
||
*/
|
||
void c_QuickSort_2Way_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;
|
||
c_OptQuickSortRecursive(array_base, 0, num - 1, size, cmp, args);
|
||
}
|
||
|
||
|
||
/* ------------------------------------------------------------------------------------------------------------------ */
|
||
/* */
|
||
|
||
/**
|
||
* @brief 内部辅助：获取两个无符号数中的较小值
|
||
*/
|
||
C_STATIC_FORCE_INLINE
|
||
c_size_t c_BM_Min(c_size_t a, c_size_t b) {
|
||
return (a < b) ? a : b;
|
||
}
|
||
|
||
/**
|
||
* @brief Bentley-McIlroy 三路划分与递归控制核心（完全规避 c_size_t 下溢）
|
||
*/
|
||
static void c_QuickBentleyMcIlroyRecursive(char* array_base, c_size_t low, c_size_t high, c_size_t size, c_SortCompare_t cmp, void* args) {
|
||
if (low >= high) {
|
||
return;
|
||
}
|
||
|
||
// 🌟 影子副本加固：将当前首位元素拷贝到局部栈缓冲区，绝缘数据别名覆盖污染
|
||
char pivot_buf[size];
|
||
memcpy(pivot_buf, array_base + (low * size), size);
|
||
|
||
// 声明游标与边界控制（采用开区间或前置递增边界控制）
|
||
c_size_t i = low;
|
||
c_size_t j = high + 1;
|
||
|
||
c_size_t p = low; // p 维护左侧等于区的右边界
|
||
c_size_t q = high + 1; // q 维护右侧等于区的左边界
|
||
|
||
while (1) {
|
||
// 1. 左游标 i 向右单调扫描，遇到大于或等于枢轴的元素时停止
|
||
do {
|
||
i++;
|
||
} while (i <= high && cmp(array_base + (i * size), pivot_buf, args) < 0);
|
||
|
||
// 2. 右游标 j 向左单调收缩，遇到小于或等于枢轴的元素时停止
|
||
do {
|
||
j--;
|
||
} while (j >= low && cmp(array_base + (j * size), pivot_buf, args) > 0);
|
||
|
||
// 如果指针发生重合或交叉，说明中间两路扫描完全汇合
|
||
if (i >= j) {
|
||
break;
|
||
}
|
||
|
||
// 3. 交换 i 和 j 处的乱序元素（基础双路快排动作）
|
||
c_QS_Swap(array_base + (i * size), array_base + (j * size), size);
|
||
|
||
// 4. 【Bentley-McIlroy 核心拓展】：
|
||
// 如果换到左边的新元素恰好等于枢轴，将其物理顶推暂存到数组“最左端（p位置）”
|
||
if (cmp(array_base + (i * size), pivot_buf, args) == 0) {
|
||
p++;
|
||
c_QS_Swap(array_base + (p * size), array_base + (i * size), size);
|
||
}
|
||
// 如果换到右边的新元素恰好等于枢轴，将其物理顶推暂存到数组“最右端（--q位置）”
|
||
if (cmp(array_base + (j * size), pivot_buf, args) == 0) {
|
||
q--;
|
||
c_QS_Swap(array_base + (q * size), array_base + (j * size), size);
|
||
}
|
||
}
|
||
|
||
// 5. 特殊边界重对齐：如果相遇在等于区元素上，使 i 跨过分界点
|
||
if (i == j && cmp(array_base + (i * size), pivot_buf, args) == 0) {
|
||
i++;
|
||
if (j > 0) j--;
|
||
}
|
||
|
||
// 6. 【数据归位阶段】：将两端暂存的所有等于元素整体交换回正中央
|
||
|
||
// 把左端 [low, p] 的等于元素完美换回当前分界点 j 的左侧
|
||
c_size_t left_len = p - low + 1;
|
||
c_size_t left_move = (j >= low) ? (j - low + 1) : 0;
|
||
c_size_t num_to_swap_left = c_BM_Min(left_len, left_move);
|
||
for (c_size_t k = 0; k < num_to_swap_left; k++) {
|
||
c_QS_Swap(array_base + ((low + k) * size), array_base + ((j - k) * size), size);
|
||
}
|
||
|
||
// 把右端 [q, high] 的等于元素完美换回当前分界点 i 的右侧
|
||
c_size_t right_len = high - q + 1;
|
||
c_size_t right_move = (high >= i) ? (high - i + 1) : 0;
|
||
c_size_t num_to_swap_right = c_BM_Min(right_len, right_move);
|
||
for (c_size_t k = 0; k < num_to_swap_right; k++) {
|
||
c_QS_Swap(array_base + ((high - k) * size), array_base + ((i + k) * size), size);
|
||
}
|
||
|
||
// -----------------------------------------------------------------
|
||
// 7. 纯加法单调控制分治，隔离无符号整数下溢
|
||
// 此时中央区全部由等于元素接管，我们需要向外侧递归两端的小于区与大于区：
|
||
// 小于区：[low, j - num_to_swap_left] | 大于区：[i + num_to_swap_right, high]
|
||
// -----------------------------------------------------------------
|
||
if (j >= low && j >= num_to_swap_left) {
|
||
c_size_t left_high = j - num_to_swap_left;
|
||
if (low < left_high && left_high != (c_size_t)-1) {
|
||
c_QuickBentleyMcIlroyRecursive(array_base, low, left_high, size, cmp, args);
|
||
}
|
||
}
|
||
|
||
if (i + num_to_swap_right < high) {
|
||
c_QuickBentleyMcIlroyRecursive(array_base, i + num_to_swap_right, high, size, cmp, args);
|
||
}
|
||
}
|
||
|
||
/**
|
||
* @brief 工业级泛型自适应 Bentley-McIlroy 三路划分快速排序标准对外入口
|
||
*/
|
||
void c_QuickSort_BentleyMcIlroy(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;
|
||
c_QuickBentleyMcIlroyRecursive(array_base, 0, num - 1, size, cmp, args);
|
||
}
|
||
|
||
/* ------------------------------------------------------------------------------------------------------------------ */
|
||
/* */
|
||
|
||
|
||
/**
|
||
* @brief 经典 Lomuto 划分函数（改自最简单快排，影子副本加固，安全防护）
|
||
*/
|
||
static c_size_t c_IterQS_Partition(char* array_base, c_size_t low, c_size_t high, c_size_t size, c_SortCompare_t cmp, void* args) {
|
||
// 影子副本加固：完整镜像拷贝主轴，彻底粉碎泛型对调下的地址克隆别名污染
|
||
char pivot_buf[size];
|
||
memcpy(pivot_buf, array_base + (high * size), size);
|
||
|
||
c_size_t i = low;
|
||
for (c_size_t j = low; j < high; j++) {
|
||
if (cmp(array_base + (j * size), pivot_buf, args) < 0) {
|
||
c_QS_Swap(array_base + (i * size), array_base + (j * size), size);
|
||
i++;
|
||
}
|
||
}
|
||
c_QS_Swap(array_base + (i * size), array_base + (high * size), size);
|
||
return i;
|
||
}
|
||
|
||
/**
|
||
* @brief 工业级泛型非递归快速排序（显式模拟栈控制，彻底免疫 Stack Overflow）
|
||
*/
|
||
void c_QuickSort_Iterative(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;
|
||
|
||
// 🌟 核心安全优化：对于 64 位系统，递归最大深度恒小于 64，开辟 128 长度的栈空间绝对可以闭环全球所有大数据
|
||
c_size_t stack[128];
|
||
long long top = -1; // 栈顶游标，使用有符号长整型防止自减溢出
|
||
|
||
// 将初始整轨区间的 [low, high] 闭区间边界压入显式模拟栈中
|
||
stack[++top] = 0;
|
||
stack[++top] = num - 1;
|
||
|
||
// 进入纯迭代控制状态机
|
||
while (top >= 0) {
|
||
// 出栈当前分治区间的右、左边界
|
||
c_size_t high = stack[top--];
|
||
c_size_t low = stack[top--];
|
||
|
||
// 1. 就地执行单路高抗性划分，锁定当前基准点的绝对无符号下标 pivot_idx
|
||
c_size_t pivot_idx = c_IterQS_Partition(array_base, low, high, size, cmp, args);
|
||
|
||
// 2. 模拟左分治管线：如果当前枢轴左侧还有可排空间
|
||
// 核心无符号防御：利用加法逆向控制 (low + 1 < pivot_idx) 代替传统减法，彻底切断下溢可能
|
||
bool has_left = (pivot_idx > 0 && low < pivot_idx - 1);
|
||
|
||
// 3. 模拟右分治管线：如果当前枢轴右侧还有可排空间
|
||
bool has_right = (pivot_idx < high);
|
||
|
||
// 🌟 工业级核心策略：优先将“大区间”压入栈顶，优先弹出来处理“小区间”！
|
||
// 这倒逼模拟栈的使用率呈对数律 $\mathcal{O}(\log N)$ 极限收敛，最大限度压缩运行时内存消耗
|
||
if (has_left && has_right) {
|
||
c_size_t left_len = (pivot_idx - 1) - low;
|
||
c_size_t right_len = high - (pivot_idx + 1);
|
||
|
||
if (left_len > right_len) {
|
||
// 左侧大，左侧优先压栈，右侧留着优先出栈处理
|
||
stack[++top] = low;
|
||
stack[++top] = pivot_idx - 1;
|
||
stack[++top] = pivot_idx + 1;
|
||
stack[++top] = high;
|
||
} else {
|
||
// 右侧大，右侧优先压栈
|
||
stack[++top] = pivot_idx + 1;
|
||
stack[++top] = high;
|
||
stack[++top] = low;
|
||
stack[++top] = pivot_idx - 1;
|
||
}
|
||
}
|
||
else if (has_left) {
|
||
stack[++top] = low;
|
||
stack[++top] = pivot_idx - 1;
|
||
}
|
||
else if (has_right) {
|
||
stack[++top] = pivot_idx + 1;
|
||
stack[++top] = high;
|
||
}
|
||
}
|
||
}
|