请问 函数中的last代表什么呢?

来源:百度知道 编辑:UC知道 时间:2024/06/24 11:43:16
程序如下:
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, (left + right)/2); /* 将划分子集的元素 */
last = left; /* 移到v[0] */
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);
}

void swap(int v[], int i, int j)
{
int temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
起大家帮忙详细分析一下以下各条语句的意思:
for(i = left + 1; i <= right; i++)
if (v[i] < v[left])
swap(v, ++last, i);

swap(v, left, last);
此处的last为什么要++last再进行交换呢?
此处的last被赋值为left是不是就代表last = 0了呢?
如果有个数组为93 86 75 59 90的话,那么在执行以上for循环时是不是交换v[i]和v[++last]呢,但是此处当的i= left+1 又因为last被赋值为left,那么last的值也为left+1,那么就相当于两个v[left+1]进行交换,这样不就出错了吗?怎么会这

首先你得了解快速排序的算法, 就是找一个基准, 把序列“大致排序”,使得小于基准的都在它的左边,而大于基准的都在它的右边。 然后再将左右两边分别这样排序。

所以上面的代码虽然未必很效率,但是可以看到last移动过去的位置都被交换成了小于v[left]的数, 然后这个v[left]被挪到last最后呆的位置,这样 v[last]左边全都是小于它的而右边全都是大于它的。 这就完成了快速排序的一个步骤了。

当然这里面有些不必要的交换,不过只要能完成目的就可以了,优化是另一方面的问题了