c - 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 是一个用于显示数组的迷你函数，只需一个 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);

代码将按预期工作。