快速排序 [Qsort]

快速排序 [Qsort]

在做USACO1.4 等差数列的时候，我发现如果用结构体+sort就会超时，用二维数组+qsort就能AC，所以为了不忘记Quick Sort，我还是把代码贴出来以备以后要看吧。

void qsort(int l,int r)

{

        int i=l,j=r,t,mid=b[(l+r)/2];

        do

        {

                while(b[i]<mid)i++;

                while(b[j]>mid)j--;

                if(i<=j)

                {

                        t=b[i];b[i]=b[j];b[j]=t;

                        i++;j--;

                }

        }

        while(i<=j);

        if(l<j)qsort(l,j);

        if(i<r)qsort(i,r);

再贴一下Quick Sort多关键字排序

【这里b数组优先，a数组是第二因素】

void qsort(int l,int r)

{

        int i=l,j=r,t,mid1=b[(l+r)/2],mid2=a[(l+r)/2];

        do

        {

                while(b[i]<mid1||(b[i]==mid1&&a[i]<mid2))i++;

                while(b[j]>mid1||(b[j]==mid1&&a[j]>mid2))j--;

                if(i<=j)

                {

                        t=a[i];a[i]=a[j];a[j]=t;

                        t=b[i];b[i]=b[j];b[j]=t;

                        i++;j--;

                }

        }while(i<=j);

        if(l<j)qsort(l,j);

        if(i<r)qsort(i,r);

}