博客

学习笔记，仅供参考！若有错误，还请指正。

题目：

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

输入：第一行包含两个整数 n 和 k。第二行包含 n 个整数（所有整数均在11~10^9范围内）。

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

代码：

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n,k,a[N];
void quicksort(int a[],int l,int r,int k)
{
	int i,j,t;
	i = l;
	j = r;
	t = a[l];
	if(l>=r){
		cout<<a[l];
		return;
	}
	if(l < r){
		while(i < j){
			while(i < j && a[j] >= t)
				j --;
			a[i] = a[j];	
			while(i < j && a[i] <= t)
				i ++;
			a[j] = a[i];
		}
		a[i] = t;	
		if(i == k - 1)	cout << a[i];
		else{
			if(i < k - 1)	quicksort(a,i + 1,r,k);
			else	quicksort(a,l,i,k);
		}
	}	
}
int main()
{
	cin >> n >> k;
	for(int i = 0;i < n;i ++)	
		cin >> a[i];
	quicksort(a,0,n-1,k);
	return 0;	
}

知识点：

两个嵌套的 while 循环后面的赋值语句实际是起到交换两个数的作用。跳出大的 while 循环后，令 a [ i ] = t ，是为了存储该数。

else 中利用递归函数，直到有输出结束，注意分成两部分后，其下标合起来是整个数列的下标序列，这是与单纯的快排算法的不同之处。单纯的快排是以基准点为中心分成两部分，然后分别进行再次快排，基准点没有再次参与排序，在该题中要参与。因为它是要查询。