+ -
当前位置:首页 → 问答吧 → 菜鸟求助:关于C++快速排序法

菜鸟求助:关于C++快速排序法

时间:2011-12-08

来源:互联网

不说废话直接上程序,这个程序是我从网上复制的有些地方看不懂。麻烦大家给我解答,顺便写个带详细注释的快速排序法的例子。

void qsort(int a[],int left,int right)
{
int pivot=a[(right+left)/2],l=left,r=right,t;

while(l<r)
{
while(a[l]<pivot)
{
++l;
}
while(a[r]>pivot)
{
--r;
}
if(l<=r)
{
t=a[r];
a[r]=a[l];
a[l]=t;
}
}
if(l==r) ?????这个地方为什么还会出现l==r,上面都有if(l<=r) 下面这语句能执行到吗?
{
l++;
}
if(left<r)
{
qsort(a,left,r-1);
}
if(l<right)
{
qsort(a,r+1,right);
}

}

作者: zjazja1234   发布时间: 2011-12-08

C/C++ code

void qsort(int a[],int left,int right)
{
    int pivot=a[(right+left)/2],l=left,r=right,t;

    while(l<r)
    {
        while(a[l]<pivot)
        {
            ++l;
        }
        while(a[r]>pivot)
        {
            --r;
        }
        if(l<=r)
        {
            t=a[r];
            a[r]=a[l];
            a[l]=t;
        }
    }
    // ?????这个地方为什么还会出现l==r,上面都有if(l<=r) 下面这语句能执行到吗?
    // if(l<=r) 语句里面没有对l、r进行改变,最外层的while是l<r,怎么不会执行到这里?
    if(l==r) 
    {
        l++;
    }
    if(left<r)
    {
        qsort(a,left,r-1);
    }
    if(l<right)
    {
        qsort(a,r+1,right);
    }
}


作者: seucs   发布时间: 2011-12-08

那上面那样做有什么作用或者说什么情况下这句语句才起作用,作用的效果又是什么?

作者: zjazja1234   发布时间: 2011-12-08

楼主自己边调试边体验算法吧

作者: quwei197874   发布时间: 2011-12-08