k＆amp; r QuickSort问题

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。

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

编辑： 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_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＆amp; r知道他们在做什么。
• 我们可以进一步假设标准库中Qsort的作者也知道他们在做什么。

因此，我们应该查看 you 撰写的第一个地方。那你真正的作者是什么。打印功能，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呼叫查看OK（基本地址和长度有效）。
• 调用QSort是无关的，显然还可以。

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

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

检查算法，k＆amp; r函数期望：

• 阵列基础地址（确定）
• 分区中第一个分类的索引，在这种情况下，在这种情况下进行排序。 0 。 （确定）
• 分区中的最后一个索引。嗯...

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

修复了这一点：

qsort_1(a, 0, arr_len-1);

代码将正常工作。