指针和数组混淆的 K&R Qsort 示例

我发现很难理解下面的代码片段。我理解所显示的指向函数风格的指针，但我发现混乱之处在于指示的行中。

void qsort(void **v, int left, int right, int (*comp) (void *, void *))
{
    int i, last;
    void swap(int **v, int i, int j);

    if (left >= right)   /* do nothing if array contains */
        return;           /* fewer than two elements */
    swap(v, left, (left + right)/2);   /* move partition elem */ [1]
    last = left;                       /* to v[0] */ [2]
    for (i = left + 1; i <= right; i++) /* partition */ [3]
        if ((*comp) (v[i], v[left]) < 0) [4]
            swap(v, ++last, i); [5]
    swap(v, left, last);        /* restore partition elem */ [6]
    qsort(v, left, last - 1); [7]
    qsort(v, last + 1, right);  [8]

}

有人可以向我解释这个例程，特别是指示的行，只需告诉我它在做什么，因为我无法弄清楚这个 qsort，我在阅读 k&r 时阅读的爱斯基摩指南说 qsort 例程是垃圾，而且过于复杂。我只需要理解为什么这样写，因为这对我来说毫无意义。

感谢您阅读本文，即使没有任何意义。

这是一段漂亮的代码！

首先，了解快速排序背后的想法很重要：

1）列出一个数字。

2）选择一个，称之为X。

3) 制作两个列表，其中一个是所有小于 X 的数字，另一个是所有大于 X 的数字。

4）对小于X的数进行排序。对大于X的数进行排序。

这个想法是，如果我们幸运地为 X 选择一个好的值，那么小于 X 的数字列表的大小与大于 X 的数字列表的大小相同。如果我们从 2*N+1 个数字开始，那么我们得到两个包含 N 个数字的列表。每次，我们希望除以二，但我们必须对 N 个数字进行排序。我们可以将 N 除以 2 多少次？这就是 Log(N)。 所以，我们排序 N Log(N) 次。这很棒！

至于代码是如何工作的，这里是运行过程，还有一些草图。我们将选择一个小数组:)

这是我们的数组：[DACBE]

开始时，left=0，指向D。right=4，指向E。

现在，按照代码和标签进行操作：

[1] 交换(v,0,2) [DACBE] -> [CADBE]

我们已经交换了选择的值并将其放在数组的开头。

[2]最后=0

这有点聪明……我们想保留一个计数器，这样我们就知道哪些值更大，哪些值更小……你会看到这是如何进展的

[3] 对于 (i=1;i

对于列表中的所有剩余元素...

[4] if ((*comp)(v[i], 'C')

如果 i 处的值小于“C”...

[5] 交换(v,++last,i);

把它放在列表的开头！

让我们运行 3,4,5 的代码

i=1:

[CADBE]

如果（'A'

swap('A','A') （最后递增！）

[CADBE]->[CADBE]（无变化）

last=1

i=2:

[CADBE]

如果 ('D'

失败了。继续前行。

i=3:

[CADBE]

如果（'B'

swap('B','D') 最后递增！

[CADBE] -> [CABDE]（看！正在排序！）

last=2

i=4:

[CABDE]

如果 ('E'

失败了。继续前行。

好吧，艾斯。这样循环给出的是 [CABDE], last=2 ('B')

现在第 [6] 行...swap(left,last)...即 swap('C','B') [CABDE] -> [BACDE]

现在，它的神奇之处在于......它是部分排序的！ BA

现在我们对子列表进行排序！

[7] -> [BA] -> [AB]

so

[BACDE] -> [ABCDE]

[8]-> [德语]->[德语]

so

[ABCDE] -> [ABCDE]

我们就完成了！