c - c 中用户定义的通用快速排序

Question

QuickSort 函数，它使用比较器来比较不同类型的数据类型

我的疑问-

->我们可以将整数数组或字符数组作为 void* 传递吗

->如果是....在传递到我的快速排序函数之前，我应该如何在主函数中类型转换

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



int compareInt(void * a, void *b) {


    if (*(int*)a > *(int*)b)

       return 1;

    else if (*(int*)a < *(int*)b)
       return -1;

    return 0;

}

int compareFloat(void * a, void *b) {

     if (*(float*)a > *(float*)b)

         return 1;

     else if (*(float*)a < *(float*)b)
        return -1;


     return 0;
}

int compareChar(void * a, void *b) {

    if (*(char*)a >*(char*)b)

        return 1;

    else if (*(char*)a < *(char*)b)
        return -1;

    return 0;
}



void quickSort(void** A, int left, int right,int (*compare)(void*,void*)) {

    void* temp;

    if (right <= left) 
        return;

    if (compare(A[right],A[left]) < 0) {

    temp = A[right];
    A[right] = A[left];
    A[left] = temp;
}

int pLow = left + 1;
int pHigh = right - 1;
int i = left + 1;

while (i <= pHigh) {

    if (compare(A[i],A[left]) < 0) {

        temp = A[i];
        A[i++] = A[pLow];
        A[pLow++] = temp;
    }
    else if (compare(A[right],A[i]) < 0) {
        temp = A[i];
        A[i] = A[pHigh]; 
        A[pHigh--] = temp;
    }
    else i++;
}

temp = A[left];
A[left] = A[--pLow];
A[pLow] = temp;

temp = A[right];
A[right] = A[++pHigh];
A[pHigh] = temp;

quickSort(A, left, pLow - 1,compare);

if (compare(A[pLow],A[pHigh]) < 0) 
    quickSort(A, pLow + 1, pHigh - 1,compare);

quickSort(A, pHigh + 1, right,compare);
}

主要功能- 不转换为 void** ；我可以将它作为 void* 传递吗？

 int main(void){


    int arr1[12] = { 2, 1, 2, 23, 13, 3, 92, 3, 54, 65, 7, 7 };

     void** arr = (void **)malloc(sizeof(void *) * 12);
    int i = 0;

    for (i = 0; i<12; i++){
        arr[i] = (void *)&arr1[i];
        printf("\n%d",arr[i]);
   }

   //int (*compare)(void*,void*) = &compareFloat;

    quickSort(arr, 0,11,&compareInt);


    printf("\n%d",*(int *)arr1[3]);

   } 

Answer 1

在 qsort 之后为您的 quickSort API 建模:

void qsort(
    void* A
,   size_t count
,   size_t size
,   int (*compare)(const void*,const void*)
);

您的 API 缺少的是 size 参数，它告诉您表示数组的单个元素的内存块有多大。这就是为什么您错误地向 void* 添加了一个不必要的星号，使 A 成为 void**。

在使用 void* 时，您必须解决两个问题 - 获取第 i 元素的位置，以及交换元素 i和 j。以下是您的操作方法:

// Get A[i]
void *ptrAi = ((char*)A)+(i*size); // Need a cast and a multiplication

// Swap A[i] and A[j]
char tmp[size]; // Make a temporary array
memcpy(tmp, ptrAi, size);          // tmp = A[i]
void *ptrAj = ((char*)A)+(j*size);
memcpy(ptrAi, ptrAj, size);        // A[i] = A[j]
memcpy(ptrAj, tmp, size);          // A[j] = tmp

现在您可以修改您的函数以将上述技术与 void* 一起使用。这将使您无需转换即可传递 int[]、float[] 和 char[] 类型的数组:

quickSort(arr, 0, 11, sizeof(int), &compareInt);