关于三路快排的一个小问题
来源:3-8 三路快速排序法
Mapple_
2019-02-25
老师您好,我想问下这个三路快排在我以下注释的地方改动一下为什么就不行了。
void Quicksort(int *arr,int l,int r)
{
if(l>=r)
return ;
int v=arr[l];
int lt=l;
int gt=r+1; //这里的改为gt=r;
int i=l+1;
while(i<gt)
{
if(arr[i]<v)
{
swap(arr[i],arr[lt+1]);
i++;
lt++;
}
else if(arr[i]>v)
{
swap(arr[i],arr[gt-1]); //这里的arr[gt-1]改为arr[gt];
gt--;
}
else
{
i++;
}
}
swap(arr[l],arr[lt]);
Quicksort(arr,l,lt-1);
Quicksort(arr,gt,r);
}
void QuickSort(int *arr,int n)
{
Quicksort(arr,0,n-1);
}
谢谢老师指点!
写回答
1回答
-
能否描述一下你修改的思路?为什么这么修改?为什么觉得这样修改是正确的?:)
022019-02-25
相似问题