c - 快速排序分区函数的参数

Question

所以我一直在尝试编写一个基于堆栈的快速排序函数，它调用分区函数。 partition() 的 header 如下:

int partition(void **A, int n, void *pivot, int (cmp)(void *, void *));

其中 A 是数组，n 是数组的大小，pivot 是主元的值(不是索引)。

我当前对分区的调用是:

partition(&A[low_int], high_int + 1, A[low_int+(high_int-low_int)/2], cmp)

上面，我的 low 和 high 值是迭代快速排序中使用的经典“l”和“h”，其中 l 开始为最低索引(h 为最高索引)。这些值会随着函数的继续而改变。

我将在下面发布我的分区函数:

int 
partition(void **A, int n, void *pivot, int (cmp)(void *, void *)) {
    int k;

    int i = 0;
    for (int j = 0; j <= n-2; j++) {
        if (cmp(A[j], pivot) <= 0) {
            i++;
            swap(A, i, j);
        }
    }
    swap(A, i+1, n-1);
    k = i + 2;
    return k; //k is the first value after the pivot in partitioned A

}

我的问题是决定调用partition()的输入。对于第一个参数，我选择了 &A[low_int]，因为我没有使用“left”作为输入之一，因此我尝试创建一个指针以稍后启动我的数组。第三个参数是枢轴，我一直在尝试选择该范围内的元素，但是这个和参数 1 都导致我的代码返回未排序的数组或无限运行。

我可以在这里获得一些关于我做错了什么以及如何修复它的帮助吗？

我已尝试包含所有相关代码，但如果我错过了任何重要内容，或者我编写的任何内容不清楚，或者您需要更多信息，请告诉我。谢谢

Answer 1

考虑一下，如果 low_int 为 1000，high_int 为 2000，并且数组以 2000 结尾，会发生什么情况。现在您给它数组 B = &A[1000] 和值 2001。值 2001 导致它访问元素 B[2001-1] = B[2000] = A[3000]。它访问数组越界。

你不应该使用像high_int - low_int + 1这样的东西作为第二个参数吗？注意:我还没有验证您的代码在参数 high_int - low_int + 1 上没有相差一的错误，但无论如何在我看来您应该减去 low_int 来自 high_int。

另一种选择是给它 A、low_int 和 high_int。