C语言通用快速排序qsortg异常：元素重复缺失问题求助

核心错误分析 #

你的qsortg出现元素重复、丢失的问题，根源有三个关键错误：

1. 基准元素交换逻辑完全错误

在partition_g函数中，你试图交换T[swap_index]和T[right]，但代码逻辑完全颠倒：

// 错误的交换逻辑
memcpy(y, (Tbyte + swap_index * width), width);
memcpy((Tbyte + swap_index * width), (Tbyte + right * width), width);
memcpy((Tbyte + right * width), (Tbyte + swap_index * width), width);

这段代码执行后，T[right]会被设置成T[swap_index]被覆盖后的内容（也就是T[right]本身），等于完全没做交换，导致后续分区使用的基准元素错误。

正确交换逻辑：应该把临时保存的y（原T[swap_index]）写入T[right]：

memcpy(y, Tbyte + swap_index * width, width);
memcpy(Tbyte + swap_index * width, Tbyte + right * width, width);
memcpy(Tbyte + right * width, y, width);

2. 比较函数不符合标准约定

你的a_strictSup_b_uint32只返回0或1，但qsort风格的比较函数要求：

• 返回负数：表示第一个参数小于第二个参数
• 返回0：表示两者相等
• 返回正数：表示第一个参数大于第二个参数

错误的返回值会让分区逻辑无法正确判断元素的大小关系，导致排序混乱。

修正后的比较函数：

int a_compare_b_uint32(const void* a, const void* b) {
    uint32_t val_a = *(const uint32_t*)a;
    uint32_t val_b = *(const uint32_t*)b;
    if (val_a < val_b) return -1;
    if (val_a > val_b) return 1;
    return 0;
}

3. 分区循环内的元素移动逻辑错误

当前循环内的memcpy操作会覆盖未处理的元素：

memcpy((Tbyte + n * width), (Tbyte + i * width), width);
memcpy((Tbyte + i * width), (Tbyte + (n-1) * width), width);

这种方式会把n-1位置的元素覆盖到i位置，但n-1位置的元素可能还没被处理，导致元素丢失、重复。

正确的分区逻辑（Lomuto 分区）：
用i标记小于等于基准元素的区域最后一个索引，遍历数组时，把小于等于基准的元素交换到左侧，最后把基准元素放到正确位置。

完整修复后的代码 #

修正后的partition_g函数

int partition_g(size_t width, void *T, int left, int right,
               int (*compareFunction)(const void *, const void *)) {

    uint8_t *Tbyte = T;
    // 随机选择基准元素索引
    uint32_t swap_index = (rand() % (right - left + 1)) + left;

    // 交换基准元素到right位置
    uint8_t *temp = malloc(width);
    if(temp == NULL) exit(-1);
    memcpy(temp, Tbyte + swap_index * width, width);
    memcpy(Tbyte + swap_index * width, Tbyte + right * width, width);
    memcpy(Tbyte + right * width, temp, width);
    free(temp);

    // 保存基准元素
    uint8_t *pivot = malloc(width);
    if(pivot == NULL) exit(-1);
    memcpy(pivot, Tbyte + right * width, width);

    int i = left - 1; // 小于等于基准的区域最后一个索引
    for (int j = left; j < right; j++) {
        // 如果当前元素小于等于基准
        if (compareFunction(Tbyte + j * width, pivot) <= 0) {
            i++;
            // 交换i和j位置的元素
            temp = malloc(width);
            if(temp == NULL) exit(-1);
            memcpy(temp, Tbyte + i * width, width);
            memcpy(Tbyte + i * width, Tbyte + j * width, width);
            memcpy(Tbyte + j * width, temp, width);
            free(temp);
        }
    }
    // 把基准元素放到正确位置
    i++;
    temp = malloc(width);
    if(temp == NULL) exit(-1);
    memcpy(temp, Tbyte + i * width, width);
    memcpy(Tbyte + i * width, Tbyte + right * width, width);
    memcpy(Tbyte + right * width, temp, width);

    free(pivot);
    free(temp);

    return i;
}

测试函数中更新比较函数调用

在test6中，把qsortg和qsort的比较函数参数改成a_compare_b_uint32：

qsortg(T,Tlen,sizeof(uint32_t),a_compare_b_uint32);
qsort(T2,Tlen,sizeof(uint32_t),a_compare_b_uint32);

测试验证 #

运行修复后的代码，输入数组[93,13,73,30,79,31,95,22,26,1]，输出结果会和标准库qsort完全一致：

input array :
[93,13,73,30,79,31,95,22,26,1]
sorted by (my qsort)qsortg :
[1,13,22,26,30,31,73,79,93,95]
Sorted by qsort :
[1,13,22,26,30,31,73,79,93,95]

内容的提问来源于stack exchange，提问作者Alexandra Turner