K&R 快速排序问题

Question

我似乎无法理解问题出在 K&R（C 编程语言第二版）的 qsort 实现中。

void qsort_1(int v[], int left, int right)
{
    int i, last;

    void swap(int v[], int i, int j);

    if (left >= right) 
            return;
    swap(v, left, (left + right)/2);
    last = left;                    
    for (i = left + 1; i <= right; i++)
            if (v[i] < v[left])
                    swap(v, ++last, i);
    swap(v, left, last);
    qsort_1(v, left, last-1);
    qsort_1(v, last+1, right);
}

这是他们的版本，我只是把它重命名为qsort_1，这样我就可以同时使用内置的了。

int arr_len = 9;

int main() {
int a[] = { 5, 5, 4, 6, 3, 7, 8, 13, 17 };
int b[] = { 5, 5, 4, 6, 3, 7, 8, 13, 17 };

    print_a(a, arr_len); // print first array
    print_a(b, arr_len); // print second array
    putchar('\n'); // space
    
    qsort(b, arr_len, sizeof(int), cmpfunc); // sort second array with standard qsort
    qsort_1(a, 0, arr_len); // sort first array with K&R qsort
    
    print_a(a, arr_len); // print first array
    print_a(b, arr_len); // print second array
    
    return 0;

}

print_a是一个显示数组的mini函数，就是一个for循环。 qsort 是官方标准实现。

我得到的输出是：

gcc -O2 -lm -o qsort qsort.c
5 5 4 6 3 7 8 13 17
5 5 4 6 3 7 8 13 17

0 3 4 5 5 6 7 8 13
3 4 5 5 6 7 8 13 17

似乎有一个前导 0 并且每次都在 K&R qsort 中删除最后一个元素。 ...帮助

void print_a(int a[], int len) {
    for (int i = 0; i < len; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}

如果需要，这里是 cmpfunc 和 print_a。

尝试用谷歌搜索这个问题，但似乎没有人遇到同样的问题。

编辑：主函数中的代码更改：

int main() {
    int a[] = { 5 , 5 ,4 ,6 ,3 ,7 ,8, 13, 17 };
    int b[] = { 5 , 5 ,4 ,6 ,3 ,7 ,8, 13, 17 };

    print_a(a, arr_len);
    print_a(b, arr_len);
    putchar('\n');

    qsort(b, arr_len, sizeof(int), cmpfunc);
    qsort_1(a, 0, **arr_len - 1**);

    print_a(a, arr_len);
    print_a(b, arr_len);

    return 0;
}

Answer 1

如有疑问，请查看您您写的代码。

我们可以暂时假设 K&R 知道他们在做什么。
我们可以进一步假设标准库中 qsort 的作者也知道他们在做什么。

因此，首先我们应该看看您创作的内容。那么你真正创作了什么。打印函数、qsort 比较器，以及 main 中的所有内容。快速回顾显示：

print_a当然可以，前提是基地址和长度是有效的（并且它们在这个用例中），所以就这样了。
qsort 比较器似乎是正确的，因为 (a) 它有效，并且 (b) 它与完全不相关的函数 qsort_1 的可疑输出无关。这样就结束了。

那只剩下 main。在该功能中，我们有：

int main() 
{
    int a[] = { 5, 5, 4, 6, 3, 7, 8, 13, 17 };
    int b[] = { 5, 5, 4, 6, 3, 7, 8, 13, 17 };

    print_a(a, arr_len); // print first array
    print_a(b, arr_len); // print second array
    putchar('\n'); // space
    
    qsort(b, arr_len, sizeof(int), cmpfunc); // sort second array with standard qsort
    qsort_1(a, 0, arr_len); // sort first array with K&R qsort
    
    print_a(a, arr_len); // print first array
    print_a(b, arr_len); // print second array
    
    return 0;

}

来自这里：

数组声明肯定没问题。
print_a 调用检查正常（基地址和长度有效）。
对qsort的调用是无关的，显然没问题。

整个程序中只剩下一行代码可能是罪魁祸首：

qsort_1(a, 0, arr_len); // sort first array with K&R qsort

检查算法，K&R 函数期望：

数组基地址(ok)
要排序的分区中的第一个索引，在本例中为 0。（好的）
要排序的分区中的最后一个索引。嗯...

这就是问题所在。 arr_len 不是最后一个索引。它是序列的长度。由于 C 中的数组是基于 0 索引的，因此最后一个索引是 arr_len-1，而不是 arr_len.

修正：

qsort_1(a, 0, arr_len-1);

代码将起作用 as-expected。

K&R 快速排序问题

K&R Quicksort issue

c

kernighan-and-ritchie

qsort