C语言通用二分插入排序崩溃：数组单元大小异常原因排查

核心错误分析 #

1. 指针数组地址计算完全错误 #

你在代码中使用(*arr) + j*data_size来定位数组元素，但*arr是数组第一个元素的值（比如示例中arr[0]是字符串"a"的内存地址），而非指针数组本身的内存起始地址。

指针数组的基地址是arr变量本身，正确的第k个元素的内存地址应该是(char*)arr + k * data_size：

• arr是void**类型，转换为char*后可以按字节偏移
• 每个元素占data_size字节（示例中是sizeof(char*)=4）

调试时arr[1]-arr[0]结果为2，是因为你取的是字符串字面量"a"和"b"的地址差（部分编译环境中字符串字面量连续存储，间隔2字节），而非指针数组元素之间的间隔，这直接导致你访问了错误的内存区域，触发崩溃。

2. 元素移动逻辑错误 #

你当前的代码试图通过交换arr[j]和arr[j+1]来移动元素，这是完全错误的：二分插入排序只需将pos到explored-1的元素向后平移一位即可，无需交换——因为current已经保存了arr[explored]的原始值，最后只需将current写入pos位置。循环内反复malloc/free也会造成不必要的内存开销和风险。

修复后的完整代码 #

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

typedef int (*compFunc)(const void*, const void*);

int binary_search(void **arr, void *item, long start, long end, int data_size, compFunc compare)
{
    long s = start, e = end;
    while (s <= e)
    {
        long middle = s + (e - s) / 2;
        int comparison = compare(item, arr[middle]);
        if (comparison == 0)
            return middle;
        else if (comparison > 0)
            s = middle + 1;
        else
            e = middle - 1;
    }
    return s;
}

void binary_insert_sort(void **arr, long arr_size, int data_size, compFunc compare)
{
    long explored, pos;
    // 按元素实际大小分配内存，而非固定sizeof(void*)
    void *current = malloc(data_size);
    if(!current){
        perror("Error allocating memory");
        exit(EXIT_FAILURE);
    }

    for (explored = 1; explored < arr_size; explored++)
    {
        // 保存当前要插入的元素
        memcpy(current, (char*)arr + explored*data_size, data_size);
        // 查找插入位置
        pos = binary_search(arr, current, 0, explored - 1, data_size, compare);

        // 将pos到explored-1的元素向后平移一位
        long j;
        for (j = explored - 1; j >= pos; j--)
        {
            memcpy((char*)arr + (j + 1)*data_size, (char*)arr + j*data_size, data_size);
        }

        // 将当前元素插入目标位置
        memcpy((char*)arr + pos*data_size, current, data_size);
    }
    free(current);
}

// 字符串比较函数示例
int string_compare(const void *a, const void *b)
{
    return strcmp(*(const char**)a, *(const char**)b);
}

// 字符串数组打印函数示例
void print_string_array(char **arr, int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%s ", arr[i]);
    }
    printf("\n");
}

int main(int argc, char const *argv[])
{
    char* arr[] = {"a", "b", "f", "d", "c", "g", "e", "1"};
    int n = sizeof(arr)/sizeof(char*);

    binary_insert_sort((void**)arr, n, sizeof(char*), string_compare);
    print_string_array(arr, n);
    return 0;
}

关键修复点 #

1. 修正地址计算：用(char*)arr + k*data_size定位数组元素，确保访问的是指针数组的内存区域，而非元素指向的内存
2. 调整内存分配大小：current的分配大小改为data_size，保证能容纳任意类型的元素
3. 简化移动逻辑：直接从后往前平移元素，避免无效的交换和内存分配操作

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