例1 快速排序

此题数据量非常大，前面的算法都不奏效。这次介绍最普遍的算法——快速排序。
其实挺简单的，但需要理解语言中的递归部分。
大致过程是对于一个无序序列，找到一个数(后面简称x)，将序列中比x小的数放在左边，比x大的放在右边，
然后对左右用同样的操作，直到操作完成。
怎么选x呢？随便选。对，你没听错，就是随便选。。。
选好后，左边找到第一个比x大的，右边找到第一个比x小的，交换；
继续进行相同的操作……实现如下：

void qsort(int a[],int l,int r)
{
    int i=l,j=r,flag=a[(l+r)/2];
    do
    {
        while(a[i]<flag) i++;
        while(a[j]>flag) j--;
        if(i<=j)
            swap(a[i],a[j]);
    }while(i<=j);
    if(l<j) qsort(a,l,j);
    if(i<r) qsort(a,i,r);
}

在极端情况下，快排时间复杂度是O(n^2)，但如果随机选x，很难出现这种。
实际上随机的算法复杂度为O(nlogn)，空间复杂度是O(n)。快排还利用了“分治”思想，
后面还会介绍归并排序。

例2 第k个数
虽然可以先排一遍，直接定位第k个，但算法复杂度为O(nlogn)。
借鉴分治思想，可降到O(n)。和快排一样，任意取x，左边的部分不大于右边。
k在哪边就递归哪边，都不属于可直接给出答案，代码如下：

int ans=0,k;
void findkth(int a[],int l,int r)
{
    if(l==r)
    {
        ans=a[l];
        return;
    }
    int i=l,j=r,flag=a[(l+r)/2];
    do
    {
        while(a[i]<flag) i++;
        while(a[j]>flag) j--;
        if(i<=j)
        {
            swap(a[i],a[j]);
            i++;j--;
        }
    }while(i<=j)
    if(k<=j) findkth(a,l,j);
    else if(i<=k) findkth(a,i,r);
    else findkth(a,j+1,j-1);
}

END