如何用归并排序对含结构体元素的数组排序？merge函数报错求助

原代码问题分析 #

你的merge函数存在以下关键错误，导致数组排序失败并触发断言错误：

1. 临时数组拷贝越界 #

左半部分临时数组tmp1的大小为n1+1（n1 = mid - low + 1），但拷贝循环用了for(i=0; i<=n1; i++)，这会读取record_arr[low + n1]即record_arr[mid+1]，超出了左半部分[low, mid]的范围，属于越界访问。同理，右半部分拷贝循环for(j=0; j<=n2; j++)会读取record_arr[high+1]，同样越界。

2. 哨兵位置越界且赋值错误 #

拷贝循环结束后，你尝试给tmp1[i+1]和tmp2[j+1]赋值哨兵值，但此时i已经等于n1+1（循环条件为i<=n1），tmp1[i+1]对应的索引是n1+2，远超tmp1的大小n1+1，属于越界写入。同时，哨兵应放在临时数组的最后一个有效位置（tmp1[n1]和tmp2[n2]），而非错误的偏移位置。

3. 哨兵值不符合排序逻辑 #

你将哨兵设为(struct record){0}，如果排序依据是结构体的uid（正数）升序，这个极小值会导致其中一个临时数组提前耗尽时，剩余元素无法正确拷贝——哨兵会被优先选中，打断正常的剩余元素遍历。正确的哨兵应该是大于所有有效元素的值。

修正后的merge函数实现 #

#include <limits.h>

void merge(struct record *record_arr, int low, int mid, int high) {
    int i, j, k;
    int n1 = mid - low + 1;
    int n2 = high - mid;
    
    // 分配临时数组，预留哨兵位置
    struct record *tmp1 = (struct record *)allocate_memory((n1 + 1) * sizeof(struct record));
    struct record *tmp2 = (struct record *)allocate_memory((n2 + 1) * sizeof(struct record));
    
    // 拷贝左半部分[low, mid]到tmp1
    for (i = 0; i < n1; i++) {
        tmp1[i] = record_arr[low + i];
    }
    // 拷贝右半部分[mid+1, high]到tmp2
    for (j = 0; j < n2; j++) {
        tmp2[j] = record_arr[mid + 1 + j];
    }
    
    // 设置哨兵：使用大于所有有效元素的uid值（假设按uid升序排序）
    tmp1[n1].uid = INT_MAX;
    tmp2[n2].uid = INT_MAX;
    
    i = j = 0;
    // 合并两个临时数组到原数组
    for (k = low; k <= high; k++) {
        // cmp_record返回-1/0表示tmp1[i]应排在前面，1表示tmp2[j]应排在前面
        if (cmp_record(&tmp1[i], &tmp2[j]) <= 0) {
            record_arr[k] = tmp1[i];
            i++;
        } else {
            record_arr[k] = tmp2[j];
            j++;
        }
    }
    
    // 注意：若allocate_memory是动态分配函数，需释放临时数组避免内存泄漏
    // free(tmp1);
    // free(tmp2);
}

关键修改说明 #

• 修正拷贝循环：将循环条件从i<=n1改为i<n1，确保只拷贝左半部分有效元素；右半部分同理改为j<n2。
• 修正哨兵位置与值：将哨兵放在临时数组的最后一个索引，使用INT_MAX作为uid值（适配uid升序排序），保证哨兵不会被优先选中，直到其中一个临时数组遍历完毕。
• 简化比较逻辑：将(cmp_record(...) ==0 || cmp_record(...) ==-1)简化为cmp_record(...) <=0，逻辑等价且更简洁。
• 内存泄漏提醒：如果allocate_memory是动态分配内存的函数，合并完成后需释放tmp1和tmp2。

归并排序整体注意事项 #

1. 确保cmp_record返回值逻辑正确：比如cmp_record(a,b)返回-1表示a应排在b前，0表示相等，1表示a应排在b后。
2. 归并排序主函数需正确划分区间，递归排序左半部分[low, mid]和右半部分[mid+1, high]，最后调用merge合并。
3. 处理边界情况：数组长度为0或1时直接返回，无需排序。

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