关于三路快排的一个小问题

来源: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回答

liuyubobobo

2019-02-25

能否描述一下你修改的思路?为什么这么修改?为什么觉得这样修改是正确的?:)

0
2
liuyubobobo
回复
Mapple_
继续加油!:)
2019-02-25
共2条回复

算法与数据结构(C++版) 面试/评级的算法复习技能包

课程专为:短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

查看课程