c - C 中的通用插入排序

Question

我用 C 语言编写了一个通用插入排序，它工作得很好。

但是，在我的插入排序函数中，它得到一个 void** arr，并在其签名上得到一个 void* arr，否则，它不起作用。

为什么会这样呢？我们还有其他方法可以将插入排序编码为通用的吗？

完整代码在这里:

#include <stdio.h>
#include <malloc.h>
#define SIZE 10
int cmp(void* elm1, void* elm2);
void insertionSort(void* arr, int size);

int main()
{
    int arr[] = {5, 8, 2, 3, 15, 7, 4, 9, 20, 13};
    int arr2[] =  {1};
    int i;
    for (i = 0; i < SIZE; i++)
        printf("%d ", arr[i]);
    printf("\n");
    insertionSort(&arr, SIZE);
    for (i = 0; i < SIZE; i++)
        printf("%d ", arr[i]);
    return 0;
}

void insertionSort(void** arr, int size)
{
    int i = 1;
    int j;
    void* temp;
    while (i < size)
    {
        if (cmp(arr[i], arr[i-1]) == -1)
        {
            temp = arr[i];
            j = i - 1;
            while (j >= 0 && cmp(arr[j], temp) == 1)
            {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
        i++;
    }
}

int cmp(void* elm1, void* elm2)
{
    if ((int)elm1 == (int)elm2)
        return 0;
    else if ((int)elm1 > (int)elm2)
        return 1;
    else 
        return -1;
}

Answer 1

由于存在多个问题，代码未定义。它恰好可以工作，因为在您的系统上，指针的大小与 int 类型的大小相同。

如果没有警告(如果启用它们)，您的代码将无法编译。函数insertionSort 和它的原型(prototype)必须具有相同的类型。

您应该将函数定义中的类型更改为

void insertionSort(void* arr, int size)

然后将指针 arr 转换为适当的类型。由于这是通用排序，如 qsort()，唯一现实的选择是强制转换为 char*。这意味着您还必须将类型的大小传递到函数中，以便指针可以正确递增。这将需要您彻底改变该功能。

所以，函数原型(prototype)应该与 qsort 相同:

void Sort(void* arr, size_t size , size_t object_size , int(*)( const void* , const void* ))