网课：第三章递归与分治思想---快速排序及相关运用

原理

数组中选择一个基准（随意），然后让左边的数小于基准，右边的数大于基准。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
int a[1000];
void kp(int l,int r){
	int mid=(l+r)/2;
	int x=a[mid];//基准可能会改变位置 
	int i=l,j=r;
	while(i<=j){
		while(a[i]<a[mid]) i++;
		while(a[j]>a[mid]) j--;
		if(i<=j){
			swap(a[i],a[j]);
			i++,j--;
		}
	}
	if(l<j) kp(l,j);
	if(i<r) kp(i,r);
}
int main() {
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	kp(0,n-1);
}

应用

NC207028第k小数

题目描述

给你一个长度为n的序列，求序列中第k小数的多少。

输入描述:

多组输入，第一行读入一个整数T表示有T组数据。

每组数据占两行，第一行为两个整数n，k，表示数列长度和k。

第二行为n个用空格隔开的整数。

输出描述:

对于每组数据，输出它的第k小数是多少。

每组数据之间用空格隔开

示例1

输入

复制2 5 2 1 4 2 3 4 3 3 3 2 1

2
5 2
1 4 2 3 4
3 3
3 2 1

输出

复制2 3

2
3

备注:

t≤10,1≤n≤5×106,k≤n,数列里每个数都在int范围内t \leq10 , 1\leq n\leq5\times 10^6,k\leq n,数列里每个数都在int范围内t≤10,1≤n≤5×106,k≤n,数列里每个数都在int范围内

由于输入比较多，请使用快读读取。

例如：

inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

做法

单纯用sort会超时，那么我们就要优化。

我们想想快排，它是每次分两个区间排序，左边小于基准，右边大于基准，我们求的是第k小的数，那么我们每次只对一定含有第k小的数的区间排序，即若左区间的数大于等于k,就递归到区间；反之递归到右区间。

要注意的是，必须先判断左区间，再判断右区间。因为当左右区间的个数都大于k，那必然是取左区间。

#include<bits/stdc++.h>
using namespace std;
int t,n,k;
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
void kp(int l,int r,vector<int> &v){
    int mid=(l+r)/2;
    int x=v[mid];
    int i=l,j=r;
    while(i<=j){
        while(v[i]<x) i++;
        while(v[j]>x) j--;
        if(i<=j){
            swap(v[i],v[j]);
            i++,j--;
        }
    }
    if(j<k-1&&r>i) kp(i,r,v);//每次只排含第k小的数的区间
    else if(i>k-1&&l<j) kp(l,j,v);
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&k);
        vector<int> v(n);
        for(int i=0;i<n;i++)
            v[i]=read();
        kp(0,n-1,v);
        cout<<v[k-1]<<endl;
    }
}