为什么在我使用归并排序时，一个额外的元素被添加到我的 void** 数组中？

Question

当我使用 mergeSort 对 void** 数组进行排序时（此数组包含 void* 指向整数的指针），一个额外的 1 （一个新元素）似乎被添加到数组中。我几乎可以肯定问题出在 mergeSort 或 merge 中，因为在调用 mergeSort 之前打印我的 void** 数组时，数据是正确的（只是未排序）。这是代码。

#define SIZE 10

void mergeSort(void**, int, int);
void merge(void**, int, int, int);
int compare(void*, void*);

int main(void) {
    int array[SIZE] = { 5, 6, 3, 2, 5, 6, 7, 4, 9, 3 };
    void *voidArray[SIZE];
    int query = 1;
    void *queryPointer = &query;

    for (int j = 0; j < SIZE; j++) {
        voidArray[j] = &array[j];
    }

    printArray(voidArray);
    mergeSort(voidArray, 0, SIZE);
    printArray(voidArray);
    result = binarySearch(voidArray, 0, SIZE, queryPointer);

    if (result == -1) {
        puts("Query not found.");
        return(0);
    }

    printf("Query found at index %d.\n", result);
    return(0);
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

void mergeSort(void **array, int head, int tail) {
    if (head < tail) {
        int middle = (head + ((tail - head) / 2));
        mergeSort(array, head, middle);
        mergeSort(array, (middle + 1), tail);
        merge(array, head, middle, tail);
    }
}

void merge(void **array, int head, int middle, int tail) {
    int headLength = (middle - head + 1);
    int tailLength =  (tail - middle);
    void *headSide[headLength];
    void *tailSide[tailLength];

    for (int i = 0; i < headLength; i++) {
        headSide[i] = array[head + i];
    }

    for (int j = 0; j < tailLength; j++) {
        tailSide[j] = array[middle + 1 + j];
    }

    int k = head;
    int l = 0;
    int m = 0;
    while (l < headLength && m < tailLength) {
        if (compare(headSide[l], tailSide[m]) == -1) {
            array[k] = headSide[l];
            l++;      
        } else {  
            array[k] = tailSide[m];
            m++;
        }
        k++;
    }

    while (l < headLength) {
        array[k] = headSide[l];
        l++;
        k++;
    }

    while (m < tailLength) {
        array[k] = tailSide[m];
        m++;
        k++;
    }
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

int compare(void *index, void *query) {
    if (*((int *)index) == *((int *)query)) {
        return (0);
    }

    if (*((int*)index) > *((int*)query)) {
        return (1);        
    }

    return (-1);
}

输出应该有未排序的数组，排序的数组，以及是否找到查询。未排序的数组中没有1，但是排序后的数组中有一个1；此外，排序结果中缺少数字 9（有趣的是，如果我对 9 执行二进制搜索，它会告诉我 9 在索引 10 处找到).

示例输出（对于 1 的查询）：

5 6 3 2 5 6 7 4 9 3
1 2 3 3 4 5 5 6 6 7

在索引 0 找到查询。

Answer 1

检查你的数组下标。

int tailLength =  (tail - middle)

tail是数组的大小，我认为tailLength不正确。

Answer 2

headSide[i] = array[head + i];

headSide[i] 是 void 而 array[head + i] 是 void*

Answer 3

margeSort 和 merge 的参数有些混乱。传递范围内最后一个元素的索引在C中不是惯用的。传递范围结束后元素的索引要简单得多，这与传递0和SIZE一致int main(): mergeSort(voidArray, 0, SIZE); 和 result = binarySearch(voidArray, 0, SIZE, queryPointer);

这是修改后的版本 API:

void mergeSort(void **array, int head, int tail) {
    if (tail - head > 1) {
        int middle = head + (tail - head) / 2);
        mergeSort(array, head, middle);
        mergeSort(array, middle, tail);
        merge(array, head, middle, tail);
    }
}

void merge(void **array, int head, int middle, int tail) {
    int headLength = middle - head;
    int tailLength = tail - middle;
    void *headSide[headLength];
    void *tailSide[tailLength];

    for (int i = 0; i < headLength; i++) {
        headSide[i] = array[head + i];
    }
    for (int j = 0; j < tailLength; j++) {
        tailSide[j] = array[middle + j];
    }

    int k = head;
    int l = 0;
    int m = 0;
    while (l < headLength && m < tailLength) {
        if (compare(headSide[l], tailSide[m]) <= 0) {
            array[k++] = headSide[l++];
        } else {  
            array[k++] = tailSide[m++];
        }
    }
    while (l < headLength) {
        array[k++] = headSide[l++];
    }
    while (m < tailLength) {
        array[k++] = tailSide[m++];
    }
}

但是请注意，使用自动存储分配临时数组 headSide 和 tailSide（又名 在堆栈上 ）对于大型数组来说是有风险的。此外，不需要将右半部分的元素保存到 tailSide 中，因为它们在复制到最终位置之前不会被覆盖。这是 merge 的更简单版本：

void merge(void **array, int head, int middle, int tail) {
    int headLength = middle - head;
    void *headSide[headLength];

    for (int i = 0; i < headLength; i++) {
        headSide[i] = array[head + i];
    }

    int k = head;
    int l = 0;
    while (l < headLength && middle < tail) {
        if (compare(headSide[l], array[middle]) <= 0) {
            array[k++] = headSide[l++];
        } else {  
            array[k++] = array[middle++];
        }
    }
    while (l < headLength) {
        array[k++] = headSide[l++];
    }
}

为什么在我使用归并排序时，一个额外的元素被添加到我的 void** 数组中？

Why is an extra element being added to my void** array when I use merge-sort?

c

mergesort

void-pointers