当前位置:C++技术网 > 资讯 > 关于快排,最简单的一种写法,有不明白的地方

关于快排,最简单的一种写法,有不明白的地方

更新时间:2016-08-19 10:04:25浏览次数:1+次

没有弄明白:在last=left之后的swap(v , ++last , i)时,v[left]的值为什么没有受到影响,left不是等于last等于0吗?在执行调换时不是将v[i]调换到v[last]吗?那么就是v[0](即v[left])处的值应该变了才对啊?


void qsort(int v[], int left, int right)
{
 int i, last;
 void swap(int v[], int i, int j);
 if (left >= right)
  return;
 swap(v, left, (right + left) / 2); 


 last = left;                      

 for (i = left + 1; i <= right; i++) 
  if (v[i] < v[left])             
   swap(v, ++last, i);         

 swap(v, left, last);               

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

C++技术网解答:

为什么在last=left之后的swap(v , ++last , i)时,v[left]的值没有受到影响,

这是因为last变量有++操作,这是先将last的值加1再传递到swap函数,所以影响到的是v[left+1]而不是v[left]。


简单说一下变量的意义:
i表示遍历整个数组的下标
last表示(当前)最后一个比left的值少的下标
left表示数组的最左边
right表示数组的最右边

left和right是不变的,每次循环,i就会加1,而last要在v[i]<v[left]的情况下才加1,即找出比v[left]小的值。


下面用画图的形式详细解释上述代码的逻辑变化