K&R Qsort示例与指针和阵列混淆

Question

我发现很难理解以下代码片段.我理解指向功能矫揉造成的指针,但我发现混淆在指示的行中.

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例程是垃圾,而且过于复杂.我只需要理解为什么它这样写,因为它对我来说没有意义.

谢谢,如果没有,请阅读此内容.

Answer 1

这是一段美丽的代码!

首先,了解quicksort背后的想法非常重要:

1)记下一个数字列表.

2)选择一个,称之为X.

3)制作两个列表,其中一个小于X的数字,以及所有数字中的一个更大.

4)对小于X的数字进行排序.对大于X的数字进行排序.

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

至于代码是如何工作的,这里是粗略的,有一点草图.我们会挑选一个小阵列:)

这是我们的阵列:[DACBE]

在开始时,左= 0,指向D.右= 4,指向E.

现在,按照代码,用您的标签:

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

我们已经将我们选择的值交换出来并将其放在数组的开头.

[2] last = 0

这有点聪明......我们想保留一个计数器,这样我们就知道哪些值更大,哪些更少...你会看到这种进展如何

[3] for(i = 1; i <= 4; i ++)

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

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

如果i的值小于'C'......

[5] swap(v,++ last,i);

把它放在列表的开头!

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

I = 1:

[CADBE]

if('A'<'C')

交换('A','A')(并且最后增加!)

[CADBE] - > [CADBE](无变化)

最后= 1

I = 2:

[CADBE]

if('D'<'C')

失败.继续.

I = 3:

[CADBE]

if('B'<'C')

交换('B','D')并最后增加!

[CADBE] - > [CABDE](看!它正在排序!)

最后= 2

I = 4:

[CABDE]

if('E'<'C')

失败.继续.

好的,王牌.所以循环给出的是[CABDE],last = 2('B')

现在行[6] ....交换(左,最后)......这是交换('C','B')[CABDE] - > [BACDE]

现在,这个的魔力是......它已经部分排序了!BA <C <DE!

所以现在我们对子列表进行排序!!

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

所以

[BACDE] - > [ABCDE]

[8] - > [DE] - > [DE]

所以

[ABCDE] - > [ABCDE]

我们完成了!

Answer 2

神奇有用的谷歌关键字：QuickSort

例如谷歌：快速排序的工作原理出现了这个解释：http://www.angelfire.com/pq/jamesbarbetti/articles/sorting/001a_HowQuicksortWorks.htm等等。

left本质上，该代码将快速排序的变体应用于指定边界和边界之间的元素right。

对于您已确定的线路：

1. 将中间元素与第left一个 ( ) 元素交换。它将成为“支点”。

2. 跟踪较大和较小元素之间的边界。这就是枢轴所属的位置。

3. 对于第一个元素之后的每个元素，
4. 如果它小于枢轴，

5. 将其移到第一个较大元素之前。

6. 将枢轴移回原位。

7. 递归地将 qsort 应用于枢轴之前的元素。（较小的）

8. 递归地将 qsort 应用于枢轴之后的元素。（较大的）

尝试自己将代码应用到数字列表中，看看它是否更有意义......