首页 / 技术问答 / C++问答列表 / 问答详情

C++ C中的通用快速排序

有谁能告诉我，在这个伪代码Quicksort&amp；之后的通用快速排序代码中，我做错了什么；Partition，该算法是有效的，因为我已经通过将int数组传递给quicksort和partition函数，在没有比较函数的情况下只对整数进行了处理，但我已经try 使其同时适用于int和字符串.在这段代码中，我只测试了int个值，但代码不起作用，输出是数组的初始值，对于字符串，我得到的是与输出相同的初始array.我对字符串部分进行了注释，因为它们的排序方式与整数相同.这是Integer working code的整数代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
//prototipi delle funzioni
typedef int (*compare_function)(const void *, const void *); 
 
void generic_quicksort(void *v, int i, int f, size_t size, compare_function compare);
void generic_swap(void *a, void *b, size_t size);
int generic_partition(void *v, int i, int f, size_t size, compare_function compare);
 
void print_int_array(const int *array, size_t len) { 
    size_t i;
 
    for (i = 0; i < len; i++) 
        printf("%d | ", array[i]);
 
    putchar('\n');
}

//funzione di confronto
int compare_int(const void *, const void *); 
 
int compare_str(const void *a, const void *b) { 
    const char **ia = (const char **)a;
    const char **ib = (const char **)b;
    return strcmp(*ia, *ib);
    /* strcmp functions works exactly as expected from
    comparison function */ 
} 
 
void print_cstring_array(char **array, size_t len) { 
    size_t i;
 
    for (i = 0; i < len; i++) 
        printf("%s | ", array[i]);
 
    putchar('\n');
} 
 
int main() {
    int v[] = { 5, 4, 3, 2, 1 };
    char *strings[] = { "Zorro", "Alex", "Celine", "Bill", "Forest", "Dexter" };

    int n = sizeof(v) / sizeof(int);
 
    print_int_array(v, n);
 
    generic_quicksort((void *)v, 0, n - 1, sizeof(int), compare_int);
    
    print_int_array(v, n);

    /*

    int s = sizeof(strings) / sizeof(*char);

    print_cstring_array(strings, s);

    generic_quicksort((void *)strings, 0, s - 1, sizeof(*char), compare_str);

    print_cstring_array(strings, s);
*/
    return 0;
} 
 
int compare_int(const void *a, const void *b) {
    return *((int*)a) - *((int*)b);
} 
 
void generic_quicksort(void *v, int i, int f, size_t size, int (*comp)(const void *, const void *)) {
    if (i >= f)
        return;
 
    int p = generic_partition(v, i, f, size, comp);
 
    generic_quicksort(v, i, p - 1, size, comp);
    generic_quicksort(v, p + 1, f, size, comp);
}
 
void generic_swap(void *a, void *b, size_t size) {
    void *tmp = malloc(size);
 
    memcpy(tmp, a, size);
    memcpy(a, b, size);
    memcpy(b, tmp, size);
 
    free(tmp);
}
 
int generic_partition(void *v, int i, int f, size_t size, int (*comp)(const void *, const void *)) {
    
    void *x = malloc(size);
    int k, j;

    memcpy(x, v + (i * size), size);

    k = i - 1;

    for (j = i; j <= f - 1; j++) {
        if (comp(v + (j * size), x) <= 0) {
            k++;
            generic_swap(v + (k * size), v + (j * size), size);
        }
    }
    
    generic_swap(v + ((k + 1) * size), v + (f * size), size);

    free(x);
    
    return (k + 1);
}

推荐答案

代码中存在多个问题:

  • int n = sizeof(v) / sizeof(int);是有风险的:关于v的类型有一个silent的假设.你应该写int n = sizeof(v) / sizeof(*v);

  • 传递切片的第一个和最后一个元素的索引的约定很混乱，在C中并不惯用，应该传递第一个元素的索引和最后一个元素之后的元素索引.这允许使用无符号索引类型和空array.

  • v + (j * size)使用void指针算法，这是并非所有系统都可用的扩展.使用unsigned char个指针.

  • 整数的比较函数对于较大的绝对值具有未定义的行为，因为减go 它们可能会导致算术溢出.你应该使用这个:

    int compare_int(const void *a, const void *b) {
    int ia = *(const int *)a;
    int ib = *(const int *)b;
    return (ia > ib) - (ia < ib);
}

  • generic_swap使用malloc和memcpy.这会给小元素带来很大的开销，您应该使用一个简单的循环:

    void generic_swap(void *a, void *b, size_t size) {
    unsigned char *pa = (unsigned char *)a;
    unsigned char *pb = (unsigned char *)b;
    while (size-- > 0) {
        unsigned char c = *pa;
        *pa++ = *pb;
        *pb++ = c;
    }
}

  • 引用中的generic_partition使用最后一个元素作为轴心，但从第一个元素初始化x.你应该写memcpy(x, v + (f * size), size);.这是导致失败的原因.目前的代码可能恰好适用于int版本.使用第一个或最后一个元素作为轴心会导致排序数组出现最坏情况.

以下是一个修改版本:

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

//prototipi delle funzioni
typedef int (*compare_function)(const void *, const void *);

void generic_quicksort(void *v, int i, int f, size_t size, compare_function compare);

//funzione di confronto
int compare_int(const void *a, const void *b) {
    int ia = *(const int *)a;
    int ib = *(const int *)b;
    return (ia > ib) - (ia < ib);
}

int compare_str(const void *a, const void *b) {
    const char *sa = *(const char * const *)a;
    const char *sb = *(const char * const *)b;
    return strcmp(sa, sb);
}

void print_int_array(const int *array, size_t len) {
    size_t i;

    if (len > 0) {
        printf("%d", array[0]);
        for (i = 1; i < len; i++)
            printf("| %d", array[i]);
    }
    putchar('\n');
}

void print_cstring_array(const char * const *array, size_t len) {
    size_t i;

    if (len > 0) {
        printf("%s", array[0]);
        for (i = 1; i < len; i++)
            printf(" | %s", array[i]);
    }
    putchar('\n');
}

static void generic_swap(void *a, void *b, size_t size) {
    unsigned char *pa = (unsigned char *)a;
    unsigned char *pb = (unsigned char *)b;
    while (size-- > 0) {
        unsigned char c = *pa;
        *pa++ = *pb;
        *pb++ = c;
    }
}

static int generic_partition(void *v, int i, int f, size_t size,
                             int (*comp)(const void *, const void *))
{
    unsigned char *p = (unsigned char *)v;
    int j, k = i;
    // using first element as pivot

    for (j = i + 1; j < f; j++) {
        if (comp(p + j * size, p + i * size) <= 0) {
            k++;
            generic_swap(p + k * size, p + j * size, size);
        }
    }

    /* swap the pivot to the end of the left part */
    generic_swap(p + i * size, p + k * size, size);
    return k;
}

void generic_quicksort(void *v, int i, int f, size_t size,
                       int (*comp)(const void *, const void *))
{
    if (f > i + 1) {
        int p = generic_partition(v, i, f, size, comp);
        generic_quicksort(v, i, p, size, comp);
        generic_quicksort(v, p + 1, f, size, comp);
    }
}

int main() {
    int v[] = { 5, 4, 3, 2, 1 };
    int n = sizeof(v) / sizeof(*v);

    const char *strings[] = { "Zorro", "Alex", "Celine", "Bill", "Forest", "Dexter" };
    int s = sizeof(strings) / sizeof(*strings);

    print_int_array(v, n);
    generic_quicksort((void *)v, 0, n, sizeof(*v), compare_int);
    print_int_array(v, n);

    print_cstring_array(strings, s);
    generic_quicksort((void *)strings, 0, s, sizeof(*strings), compare_str);
    print_cstring_array(strings, s);

    return 0;
}

请注意， Select 第一个或最后一个元素作为轴心会导致排序数组的最坏情况复杂性.generic_quicksort的递归深度将是数组的长度，可能会导致stack overflow.

下面是一个经过修改的版本，可以防止这种情况，但在排序数组中仍然具有二次时间复杂性:

void generic_quicksort(void *v, int i, int f, size_t size,
                       int (*comp)(const void *, const void *))
{
    while (f > i + 1) {
        int p = generic_partition(v, i, f, size, comp);
        if (p - i < f - p) {
            generic_quicksort(v, i, p, size, comp);
            i = p + 1;
        } else {
            generic_quicksort(v, p + 1, f, size, comp);
            f = p;
        }
    }
}

C++相关问答推荐

为什么这个C程序代码会产生以下结果？

ATTiny1606定时器TCA 0中断未触发

将 typewriter LF打印到Windows终端，而不是隐含的CR+LF

如何将字符串传递给函数并返回在C中更改的相同字符串？

在C语言中，在数学运算过程中，为什么浮点数在变量中的行为不同

将宏值传递给ARM链接器，该链接器将变量放置在特定位置

我怎么才能用GCC编译一个c库，让它包含另一个库呢？

平均程序编译，但结果不好

为什么我的Hello World EFI程序构建不正确？

如何在c中使用具有不同变量类型的内存分配？

将 struct 数组写入二进制文件时发生Valgrind错误

从整型转换为浮点型可能会改变其值.

计算SIZE_MAX元素的长数组的大小

生成的头文件不包括用户定义的文件

令人困惑的返回和 scanf 问题相关

C Makefile - 如何避免重复提及文件名

在C中定义函数指针？

UEFI 应用程序中的计时器回调仅在 AMI BIOS 中挂起

与 C 相比，C++ 中无副作用的无限循环的好处是 UB？

可以从指针数组中的值初始化指针吗？

实用课程推荐
相关教程推荐
休闲君评测 |  TOOLFK工具网 |  chrome插件网 |  古诗文网 |  良许Linux教程网 |  Python之禅 |  红色石头 |  豪评测 |  入党申请书 | 

© 2020 Hi LearnFk 意见反馈 免责声明 关于我们 桂ICP备11002319号-3 友链&广告位+QQ: 1963612630