用C编程的快速排序

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

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 ie 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之间的交换吗？

代码继续

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

Answer 1

首先，您对交换function有一个小的误解。 让我们说这个函数的原型是 –

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

交换函数交换位置数组[i]和数组[j]的数字。 因此，交换函数交换数组中的元素。 所以，线 –

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

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

 last = left; 

make，’last’指向pivot的位置（’left’），所以这里’last’= 0的值不是4.所以，循环，

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

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

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

检查当前元素（'v [i]'）是否小于枢轴（'v [left]'）。 然后，相应地交换线中的较小元素，

  swap(v, ++last, i); 

从位置（最后+ 1）到它增加的地方。 因此，'last'左边的元素小于pivot，右边的元素更大。 我想你错过了另一条线，我们将枢轴带回到算盘执行期间位于'v [left]'位置的中间位置。 然后，递归调用发挥作用。 如果您正在寻找quicksort的帮助， 这是一个很好的起点！

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