我正在try 将QSORT算法实现为C++中的泛型函数

我的函数返回一个排序数组，但它不是正确的:一些元素被复制，另一些元素被删除. 例如，以下各项的预期返回值: [93,13,73,30,79,31,95,22,26,1]个 是: [1,13,22,26,30,31,73,79,93,95] 我得到的却是这个: 一百零二

编辑:谢谢你的回答，我已经更正了你在我的代码中显示的错误. 但它仍然不起作用.我已经用测试函数完成了我的帮助请求 我还更改了变量的名称，以使它们更易于理解.

这是我的代码:

我的泛型qsort实现

分区函数，宽度:以字节为单位的值大小(1字节=8位) VOID*T:底部 左:左索引，右:右索引CompareFunction:排序顺序函数

int partition_g(size_t width, void *T, int left, int right,
               int (*compareFunction)(const void *, const void *)) {

    uint8_t *Tbyte = T;
    //uniform draw in set [d,...,f]
    uint32_t swap_index = (rand() % (right - left + 1)) + left;

    //We swap T[right] and T[swap_index]

    uint8_t *y = malloc(width);
    if(y==NULL)exit(-1);
    // y <-- T[swap_index]
    memcpy(y, (Tbyte + swap_index * width), width);
    // T[swap_index] <-- T[left]
    memcpy((Tbyte + swap_index * width), (Tbyte + right * width), width);
    // T[left] <-- T[swap_index]
    memcpy((Tbyte + right * width), (Tbyte + swap_index * width), width);

    uint8_t *x = malloc(width);
    if(x==NULL)exit(-1);
    // x <-- T[right]
    memcpy(x,Tbyte + right * width, width);

    int n = right;
    for (int i = right - 1; i >= left; i--) {
        //compare (T[i],x)
        if (compareFunction((Tbyte + i * width), x)>0)
        {
            //T[n] <-- T[i]
            memcpy((Tbyte + n * width), (Tbyte + i * width), width);
            //T[i] <-- T[n-1]
            memcpy((Tbyte + i * width), (Tbyte + (n-1) * width), width);
            n--;
        }
    }
    //T[n] <-- x
    memcpy((Tbyte + n * width), x, width);

    //free of allocate variable
    free(y);
    free(x);

    return n;
}

递归调用PARTION函数的函数

void recqsortg(void *array, size_t elementSize, 
                int (*compareFunction)(const void *, const void *),int left, int right) {
    if (right > left) {
        int n = partition_g(elementSize, array, left, right, compareFunction);

        recqsortg(array, elementSize, compareFunction, left, n - 1);
        recqsortg(array, elementSize, compareFunction, n + 1, right);
    }
}

主要功能

void qsortg(void *array, size_t elementCount, size_t elementSize,
            int (*compareFunction)(const void *, const void *)) {
    recqsortg(array, elementSize, compareFunction, 0, elementCount - 1);
}

为我的测试函数设置的函数:

int a_strictSup_b_uint32(const void* a, const void* b) {
    return (*(uint32_t*)a > *(uint32_t*)b);
}

//function to display an array of integers
void printTab_entier_g(size_t nbelem, size_t width, void * T){
    uint64_t indice_depart;
    uint64_t res;
    uint8_t un_octet;
    uint8_t * Toctet = T;

    printf("[");

    for (int i = 0; i<nbelem; i++){
        res = 0;
        indice_depart = i * width;

        // on définit la valeur de res en parcourant width octets à partir de l'indice i
        for(int j = 0; j<width; j++){
            un_octet = *(Toctet + indice_depart + j);
            res = res + ((uint64_t)un_octet << j*8);
        }
        printf("%lu",res);
        if(i<nbelem-1)printf(",");
    }
    printf("]\n");
}

//function for assigning an element to an array
void affectationg_tab_g(void* T, uint32_t indice, uint64_t number, size_t width){
    
    uint8_t * Tprime = T;
    uint64_t depart_affectation = width * indice;
    
    for(uint64_t i = 0; i < width; i++){    //Attention l'entier number est tronqué si il > width
        *(Tprime + depart_affectation + i) = (number >> i*8) & 0xFF;
    }

}

//function that initializes an array of random elements in the set [0,...,99].
void init_random_tab_g(size_t Tlen, size_t width, void * T){
    uint32_t rd_number;
    for(int i = 0; i<Tlen; i++){
        rd_number = rand()%100;
        affectationg_tab_g(T,i,rd_number,width);
    }
}

//我的测试函数

void test6()
{
    size_t Tlen = 10;
    uint32_t * T = malloc(Tlen*sizeof(uint32_t));
    uint32_t * T2 = malloc(Tlen*sizeof(uint32_t));
    init_random_tab_g(Tlen,sizeof(uint32_t),T);
    memcpy(T2,T,Tlen*sizeof(uint32_t));

    printf("input array :\n");
    printTab_entier_g(Tlen,sizeof(uint32_t),T);

    qsortg(T,Tlen,sizeof(uint32_t),a_strictSup_b_uint32);
    qsort(T2,Tlen,sizeof(uint32_t),a_strictSup_b_uint32);
    printf("sorted by (my qsort)qsortg :\n");
    printTab_entier_g(Tlen,sizeof(uint32_t),T);
    printf("Sorted by qsort :\n");
    printTab_entier_g(Tlen,sizeof(uint32_t),T2);


    free(T);
    free(T2);
}
int main(){
    //the way I initialize random
    srand(/*time(NULL)*/123);
    //how I call test6
    test6();
    return 0;
}

所有这些代码的输出是:

输入[13]: [93，13，73，30.79，31.95，22，26，1]

按(我的qort)qsortg排序: [1，1，22，26，26，26，30，30，95，95]

按qsort排序: [1，13，22，26，30，31，73，79，93，95]

其中我们可以看到我的qsortg函数为FALSE