快速排序

快速排序模板

void quick_sort(int q[],int l,in r)
{
	if(l>=r) return;
	int i=l-1,j=r+1,mid=q[i+j>>1];
	while(i<j)
	{
		do i++;while q[i]<mid;
		do j--;while q[j]>mid;
		if(i<j) swap(q[i],q[j]);
	}
	//当划分选取j时，mid不能选用q[r],否则会出现无限循环
	//当划分选用i时,mid不能选用q[l]
	quick_sort(q,l,j);
	qucik_sort(q,j+1,r);
}

以当划分选取j时为例，当mid选用去q[r]时，j最小为l,最大为r,所以quick_sort(q,j+1,r)不会超时，但是当j==r时quick_sort(q,l,j)会陷入无限循环。

例题

给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k个数。
输入格式
第一行包含两个整数 n和 k。
第二行包含 n个整数（所有整数均在 1∼109范围内），表示整数数列。

输出格式
输出一个整数，表示数列的第 k个数。

数据范围
1≤n≤100000，1≤k≤n

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6;
int a[N];
void quick_sort(int q[],int l,int r)
{
    if(l>=r)
    {
        return;
    }
    int i=l-1,j=r+1,mid=q[l+r>>1];
    while(i<j)
    {
        do{
            i++;
        }while(q[i]<mid);
        do{
            j--;
        }while(q[j]>mid);
        if(i<j)
        {
            swap(q[i],q[j]);
        }
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    quick_sort(a,0,n-1);
    printf("%d",a[m-1]);
}