K＆安培; R的qsort例如用指针和数组的困惑 [英] K&R Qsort example with Pointers and Arrays confusion
问题描述
我觉得很难理解code的片断。我理解的函数指针矫饰表现，但如果我发现混乱的指示线。
I find it difficult to understand the following snippet of code. I understand the pointer to function mannerism showed, but where I find confusion is in the indicated lines.
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例程是垃圾和过于复杂。我只需要了解它为什么这样写，因为它是没有意义的我。
Can someone explain this routine to me, especially the indicated lines, just tell me what it's doing, because I can't figure this qsort out, the eskimo guide I read whilst reading k&r said that the qsort routine is rubbish, and overly complicated. I just need to understand why it's written like this, because it makes no sense to me.
谢谢，如果什么都不缺，阅读本。
Thanks, if for nothing, for reading this.
推荐答案
这是一个美丽的一块code的！
This is a beautiful piece of code!
首先，它是重要的，你明白背后的想法快速排序：
First off, it's important that you understand the idea behind quicksort:
1）取号码列表
2）选一个，把它的X.
2) Pick one, call it X.
3）使两个列表，小于X的所有号码之一，并且所有的号码中的一个更大的
3) Make two lists, one of all the numbers smaller than X, and one of all the numbers bigger.
4）排序数字小于十排序的数字大于x
4) Sort the numbers smaller than X. Sort the numbers bigger than X.
我们的想法是，如果我们很幸运，并挑选了X中的良好的价值，那么小于X的数字列表，其大小与数量比十更大。如果我们开始与2 * N + 1的号码列表相同，那么我们得到N个号的两个列表。每一次，我们希望两分，但我们有N个数字排序。多少次我们可以整除n由两个？这是日志（N）。
所以，我们排序的n log（N）次。这是伟大的！
The idea is that if we get lucky and pick a good value for X, then the list of numbers smaller than X is the same size as the list of numbers bigger than X. If we start with 2*N+1 numbers, then we get two lists of N numbers. Each time, we hope to divide by two, but we have to sort N numbers. How many times can we divide N by two? That's Log(N). So, we sort N Log(N) times. This is great!
对于code如何工作的，这里的runthrough，用少许草图。我们会挑选一小阵：）
As for how the code works, here's the runthrough, with a little sketch. We'll pick a small array :)
下面是我们的数组：[DACBE]
here's our array: [DACBE]
在一开始，左= 0，指着D.右= 4，指着到E
at the start, left=0, pointing to D. right=4, pointing to E.
现在，继code，你的标签：
now, following the code, with your labelling:
[1]互换（V，0.2）[DACBE] - > [CADBE]
[1] swap(v,0,2) [DACBE] -> [CADBE]
我们已经换了我们选择的价值，并把它放在数组的开始。
we've swapped our chosen value out and put it at the start of the array.
[2]最后= 0
这是一个有点聪明......我们希望保持一个计数器，所以我们知道哪些值均大于和小于...你会看到这是如何进展
this is a bit clever... we want to keep a counter so we know which values were greater and which less... you'll see how this progresses
[3]为（ⅰ= 1; I＆下; = 4; i ++在）
[3] for (i=1;i<=4;i++)
有列表中的所有剩余的元素...
for all the remaining elements in the list...
[4]如果（（*对比）（ⅴ[I]中，C）小于0）
[4] if ((*comp)(v[i], 'C')<0)
如果在I的值大于CLESS ...
if the value at i is LESS than 'C'...
[5]互换（V，最后++，I）;
[5] swap(v,++last,i);
把它放在列表的开始！
让我们运行code为3,4,5
let's run the code for 3,4,5
I = 1：
[CADBE]
如果（'A'＆LT;'C'）
if ('A'<'C')
互换（'A'，'A'）（和增量即止！）
swap('A','A') (AND INCREMENT LAST!)
[CADBE] - > [CADBE]（没有变化）
[CADBE]->[CADBE] (no change)
最后= 1
我= 2：
[CADBE]
如果（'D'＆LT;'C'）
if ('D'<'C')
失败。继续前进。
我= 3：
[CADBE]
如果（'B'＆LT;'C'）
if ('B'<'C')
交换（B，D），并增加了！
swap('B','D') And increment last!
[CADBE] - > [CABDE]（！听着！它的分选）
[CADBE] -> [CABDE] (lookit! it's sorting!)
去年= 2
我= 4：
[CABDE]
如果（'E'＆LT;'C'）
if ('E'<'C')
失败。继续前进。
好吧，王牌。使得循环给出为[CABDE]，最后= 2（'B'）
Ok, ace. so that loop gives is [CABDE], last=2 ('B')
现在行[6] ....互换（左，上）......这互换（'C'，'B'）
[CABDE] - > [BACDE]
Now line [6].... swap(left,last)... that's swap('C','B') [CABDE] -> [BACDE]
现在，这个神奇的是...它部分分类！ BA＆LT; C＆LT; DE！
Now, the magic of this is... it's partially sorted! BA < C < DE!
所以，现在我们的子列表进行排序！
So now we sort the sub-lists!!
[7] - > [BA] - > [AB]
[7] -> [BA] -> [AB]
所以
[BACDE] - > [ABCDE]
[BACDE] -> [ABCDE]
[8] - > [DE] - > [DE]
[8]-> [DE]->[DE]
所以
[ABCDE] - > [ABCDE]
[ABCDE] -> [ABCDE]
和我们就大功告成了！
这篇关于K＆安培; R的qsort例如用指针和数组的困惑的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
