第k个数（快速排序）

港控/mmm° 2023-10-11 16:24 33阅读 0赞

7-5 第k个数 (20 分)

知识点：快速排序

给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。

#### 输入格式: ####

输入共两行，第一行包含整数 n和k，1≤k≤100000，1≤n≤1000000。

第二行包含 n 个整数（所有整数均在 1∼10^9 范围内），表示整数数列。

#### 输出格式: ####

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

#### 输入样例: ####

5 2
    2 5 1 4 3

#### 输出样例: ####

**算法分析：**如果是pintia上面的朋友来寻找，那么你可能需要运行个一两次， 不一定一把通过，因为这个题目的数据量比较大，所以会很容易超时，这里我们可以使用快速排序的方法进行对数据的排序，在排序的过程当中查找我们的第k个数。

#include<bits/stdc++.h>
    using namespace std;
    int a[1000000];	
    int n,k;
    int quicksort(int a[],int begin,int end,int k)
    {
    	if(begin>=end)
    		return a[begin];
    	int mid=a[(begin+end)/2];
    	int i=begin-1,j=end+1;//这里如果不是使用do while循环来实现的(因为do while循环是运行后判断)，用while时需要改成i=begin,j=end;
    	while(i<j)
    	{
    		do{
    			i++;
    		}while(a[i]<mid);
    		do{
    			j--;
    		}while(a[j]>mid);//以上是我们的快速排序，排序的过程是先右后左
    		if(i<j)
    		{
    			swap(a[i],a[j]);//swap函数交换a[i]与a[j]的value 
    		}
    	}
    	if(j-begin+1>=k) return quicksort(a,begin,j,k);//当我们的这个第k个数在左边，那么我们就直接递归左边的数据，继续快速排序
    	else return quicksort(a,j+1,end,k-(j-begin+1));//当我们查找的这个第K个数在右边，那么我们就直接帝国右边的数据，继续快速排序
    }
    int main()
    {
    
    	scanf("%d %d",&n,&k);
    	for(int i=0;i<n;i++)
    	{
    		scanf("%d",a[i]);
    	}
    	printf("%d",quicksort(a,0,n-1,k));
    	
    }