快速排序分区函数的参数

Question

所以我一直在尝试编写一个 stack-based 快速排序函数，它调用分区函数。 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 最高）。随着函数的继续，这些值会发生变化。

我将 post 我的分区函数如下：

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" 作为我的输入之一，因此我试图创建一个指针，以便稍后启动我的数组。第三个参数如果是枢轴，我一直在尝试 select 该范围内的一个元素，但是这个和参数 1 都导致我的代码 return 一个未排序的数组或运行无限。

我可以在这里得到一些帮助，了解我做错了什么以及如何解决它吗？

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

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 的差一错误，但无论如何在我看来你应该从 high_int 中减去 low_int .

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

快速排序分区函数的参数

Arguments to Partition function for Quicksort

c

arrays

partitioning

quicksort