自定义函数复刻qsort时，运行后无法打印并且调试期间出现访问冲突

Question

Swap：实现交换
cmp_char：实现char类型的比较
My_qsort：实现qsort
主函数：使用qsort并且打印使用My_qsort后的arr

Answer 1

【以下回答由 GPT 生成】

首先，我们来看为什么代码无法正确打印使用My_qsort排序后的数组arr。

在你的自定义qsort函数My_qsort中，你使用了递归调用来对数组进行分区和排序。但是，你在调用My_qsort的地方有一个小错误。在这里：

My_qsort(base, (upper - (char*)base) / size + 1, size, cmp);  // 这里应该是 (upper - lower) / size + 1

应该是将 (upper - lower) 作为参数，而不是 (upper - (char*)base) 。这个错误导致了一个访问冲突。

在你的My_qsort函数中，你还需要修改一些地方来解决访问冲突问题。在每次交换元素后，你也需要更新 pivot 的位置，以确保它指向正确的元素。在下面的代码中，我添加了对 pivot 的更新：

if (lower <= upper) {
    Swap(lower, upper, size);
    lower += size;
    upper -= size;
    pivot = lower + ((upper - lower) / size) * size;
}

接下来，我们来解决无法正确打印排序结果的问题。在你的主函数中，你调用了标准库函数qsort来对数组进行排序并打印结果，但是在调用My_qsort函数后没有打印使用自定义排序函数排序的结果。

你可以在调用My_qsort函数后，再次使用一个循环来打印数组的元素。这样你就能正确看到使用自定义排序函数排序后的结果了。

下面是修改后的代码：

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

// 实现交换
void Swap(void* a, void* b, size_t size) {
    char* temp = (char*)malloc(size);
    if (temp != NULL) {
        memcpy(temp, a, size);
        memcpy(a, b, size);
        memcpy(b, temp, size);
        free(temp);
    }
}

// 实现整型比较
int cmp_int(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

// 实现自定义的qsort
void My_qsort(void* base, size_t num, size_t size, int (*cmp)(const void*, const void*)) {
    if (num <= 1) {
        return;
    }
    char* lower = (char*)base;
    char* upper = (char*)base + (num - 1) * size;
    char* pivot = lower + (num / 2) * size;

    while (lower <= upper) {
        while (cmp(lower, pivot) < 0) {
            lower += size;
        }
        while (cmp(upper, pivot) > 0) {
            upper -= size;
        }
        if (lower <= upper) {
            Swap(lower, upper, size);
            lower += size;
            upper -= size;
            pivot = lower + ((upper - lower) / size) * size;
        }
    }

    My_qsort(base, (upper - lower) / size + 1, size, cmp);
    My_qsort(lower, ((char*)base + num*size - lower) / size, size, cmp);
}

int main() {
    int arr[] = {5, 2, 8, 4, 1, 9};
    size_t num = sizeof(arr)/sizeof(arr[0]);

    qsort(arr, num, sizeof(int), cmp_int);
    for(int i=0; i<num; i++){
        printf("%d ", arr[i]);
    }

    printf("\nUsing My_qsort:\n");
    My_qsort(arr, num, sizeof(int), cmp_int);
    for(int i=0; i<num; i++){
        printf("%d ", arr[i]);
    }

    return 0;
}

这样修改后，你应该能够正确打印出使用My_qsort排序后的数组arr，并解决访问冲突问题。

【相关推荐】

• 这篇博客: 算法基础：快排优化：为什么qsort会这么快中的 qsort的实现方式 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^