快速排序

复杂度: $O(NlogN) \sim O(N^2)$

思想：

• 确定分界值 x，从左往右找到第一个位置不对的数，再找到从右往左第一个位置不对的数，将他们交换使得两个位置都对。

• while 循环完以后会做到 [l,j]都比 x 小，[j+1,r]都比 x 大。

• 然后对左边和右边区间分别进行上述操作，因为最终都会划分到数量为 1 的区间，在这个过程中完成了所有正确位置的排放

属于 分治算法

void quick_sort(int p[],int l,int r)
{
    if(l>=r) return;
    
    int x = p[l+rand()%(r-l+1)],i = l-1, j = r+1;  // srand可以在主函数中调用之前设置，这里ij分别往后往前一单位是因为我们下面的写法里先对ij操作再判断是否符合循环条件的
    //这里l+rand()%(r-l+1)的取值范围是[l,r]
    while(i<j)
    {
        do i++ ; while(p[i]<x);
        do j-- ; while(p[j]>x);
        if(i<j) swap(p[i],p[j]);
    }
    
    quick_sort(p,l,j);  //需要注意这里的划分方法，前面j后面j+1，这是前面我们对ij的动作所决定的
    quick_sort(p,j+1,r);
}

快速选择

复杂度: $O(NlogN)$

变式：选择排序后第 k 个数

int quick_select(int p[],int l,int r,int k)
{
    if(l>=r) return p[l];  //选到最后只有一个那就是这个了
    
    int x = p[l+rand()%(r-l+1)],i=l-1,j=r+1;
    while(i<j)
    {
        do i++;while(p[i]<x);
        do j--;while(p[j]>x);
        if(i<j) swap(p[i],p[j]);
    }
    
    int sl = j - l + 1;  //主要变在这里，计算左边有多少个数看看接下来需要在左边找还是右边找
    if(k <= sl)
        return quick_select(p,l,j,k);
    else
        return quick_select(p,j+1,r,k-sl); //我们要找的是第k个数，那既然不在左边的sl个，就要找右边第k-sl个
}