用C编程的快速排序 [英] Quick sort programmed in C

问题描述

我正在阅读 K&R 的 ANSI C.我遇到了 qsort 程序.我想要一点帮助.假设我有 9 个元素，索引为 0->8.请阅读评论，看看我是否理解正确.非常感谢你的努力

I am reading ANSI C by K&R. I came across the qsort program. I want a little help. Suppose I have 9 elements with index 0->8. Please read the comments to see if I am understanding it correct or not. Thanks a lot for you efforts

void qsort(int v[] , int left, int right)
{
int i, j, last;
void swap(int v[], int i, int j);   

if(left >= right)               /*if the array has only one element return it*/
      return;
swap(v,left, (left+right)/2); /* now, left=(left+right)/2= 0+8/2= 4 we have 4 as left*/
last= left;   /* putting left = last of the first partition group i.e. last=4*/

for(i=left+1; i<=right,i++)  /* now looping from 4+1=5 to 8 with increment of 1*/
     if(v[i] < v[left])       /*if value at 5th is less than value at 4th */
          swap(v, ++last, i);  

我在最后一个交换步骤中遇到问题.正如我的值建议交换 ++4 即到 i 即 4+1= 5(用 5 交换 5 位置?).我怎么能理解这一点?4 和 5 之间一定有交换，而不是 5 和 5 是吗?

I have problem in this last swap step. As my values suggest swap ++4 i.e. to i i.e. 4+1= 5 (swapping 5 position with 5?). How can I understand this? There must be a swapping between 4 and 5, not 5 and 5 is it?

代码继续

swap(v,left, last);
qsort(v,left,last-1);
qsort(v,last+1,right);
}

推荐答案

首先，您对交换功能有一个小小的误解.假设函数的原型是 -

Firstly, you have a small misconception about the swap function. Let's say the prototype of the function is -

swap(int array[], int i, int j)

swap 函数交换位置 array[i] 和 array[j] 处的数字.因此，swap 函数交换数组中的元素.所以，线 -

The swap function swaps the numbers at location array[i] and array[j]. So, the swap function swaps the elements in the array. So, the line -

swap(v, left, (left + right) / 2);

意味着，数组中的中间元素与最左边的元素交换.显然，快速排序以中间元素为轴心.这种交换对局部变量或参数没有影响.根据您的数据输入示例，'left' 的值 = 0，right 的值 = '8'，即使在交换之后也是如此.这就是你感到困惑的地方.交换数组的元素，而不是变量的值.所以，现在，这条线 -

Means that, the middle element in the array is swapped with the leftmost element. Clearly, the quicksort is taking the middle element as the pivot. This swap has no effect on the local variables or parameters. According to your data input example, the value of 'left' = 0, and the value of right = '8', even after the swapping. This is where you got confused. The elements of array are swapped, not the values of variables. So, now, the line -

last = left;

使，'last' 指向枢轴的位置('left')，所以这里的值 'last' = 0 而不是 4.所以，循环，

makes, 'last' point to the location of the pivot ('left'), so here the value of 'last' = 0 not 4. So, the loop,

for(i = left + 1; i <= right; i++) 

从 i = 1 到 8 运行.顺便说一句，你忘记了分号..！然后，该行，

Runs from i = 1 to 8. BTW, you forgot the semicolon..! Then, the line,

if(v[i] < v[left])

检查当前元素 ('v[i]') 是否小于枢轴 ('v[left]').然后，相应地交换较小的元素，如行中，

checks if the current element ('v[i]') is less than the pivot ('v[left]') or not. Then, accordingly swaps the lesser elements as in the line,

 swap(v, ++last, i);

从位置(最后一个 + 1)到它增加到的位置.因此，'last' 左边的元素小于枢轴，右边的元素更大.我认为您错过了另一行，在该行中，我们将枢轴返回到算法执行期间位于v[left]"位置的中间.然后，递归调用发挥它们的作用.如果您正在寻求快速排序方面的帮助，这个是个好地方开始吧！

from the location (last + 1) till where ever it increments to. So, the elements to the left of 'last' are less than pivot and the elements to the right are greater. I think you are missing another line, where we bring the pivot back to the middle which was at the location 'v[left]' during the execution of the algorithm. Then, the recursive calls play their roles. If you are looking for help with quicksort, this is a good place to start !

希望我的回答对您有所帮助，如果有帮助，请告诉我..！☺

I hope my answer has helped you, if it did, let me know..! ☺

这篇关于用C编程的快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！