arrays - C 编程语言中的 qsort 函数如何工作

Question

我正在阅读 Brian W. Kernighan 和 Dennis M. Ritchie 所著的《C 编程语言》。 我已经读到第 5.6 章，他在其中解释了使用指向指针的指针的 shell 排序函数。

在他给出的代码示例中，我不明白 qsort 函数是如何工作的: 据我了解，++last将等于i？我们在这里交换同一个单元格吗？这对我来说没有意义。

这是两个函数的代码:

/* qsort: sort v[left]...V[right] into increasing order */
void qSort(void *v[], int left, int right, funcP comp)
{
    int i, last;

    void swap(void *v[], int, int);

    if (left >= right)             /* do nothing if array contains */
        return;                    /* fewer than two elements */
    swap(v, left, (left + right) / 2);
    last = left;
    for (i = left + 1; i <= right; i++)
        if ((*comp)(v[i], v[left]) < 0)
            swap(v, ++last, i);
    swap(v, left, last);
    qSort(v, left, last - 1, comp);
    qSort(v, last + 1, right, comp);
}

}

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

    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}```

Answer 1

I'm reading The C Programming Language by Brian W. Kernighan and Dennis M. Ritchie. I've reached chapter 5.6, where he explains the shell sort function using pointers to pointers.

请注意，问题中提供的代码实现了快速排序算法，而不是希尔排序。

I'm not getting, in the code example he gives, how the qsort function works: from what I understood, ++last will be equal to i?? Are we here swapping the same cell?? It's not making a sense for me.

++last 可能等于 i。在这种情况下，交换没有净效应。但当比较函数第一次返回大于或等于 0 的结果时，i 将增加，而 last 不会增加(请注意 if code> 语句)，因此 i 等于 last + 2。对于 qsort 执行的其余部分，i 将至少比 last 提前那么远，因此 ++last 不等于i。对于随机数据，通常会有很多这样的事件，因此 i 继续领先 last 越来越远。

总的来说，该函数将给定的数组元素重新排列为两组，其中一组的所有元素都小于或等于另一组的所有元素。然后它递归地对刚刚形成的两个组中的每一个执行相同的工作。