[快速排序,分治算法] 求第 k 小的数

求第 k 小的数

题目描述

输入 $n$（$1\le n<5000000$ 且 $n$ 为奇数）个数字 $a_i$（$1\le a_i<{10}^9$），输出这些数字的第 $k$ 小的数。最小的数是第 $0$ 小。

请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。

输入格式

输出格式

样例 #1

样例输入 #1

5 1
4 3 2 1 5

样例输出 #1

2

解题分析
由于数据量巨大，简单的冒泡排序是无法胜任的，故考虑更加优秀的快速排序，然而，由于只要求出第k小的树，所以我们只要递归分治地去排序k所在的区间即可，这样又可以极大减少运算量，最终满足时间要求。

代码实现

#include <iostream>
using namespace std;
int a[5000000]; int k,ans;

void qsort(int begin,int end){
	if(begin==end) {
		ans=a[begin];
		return;
	}
	int i=begin,j=end,flag=a[(i+j)/2],temp;
	do{
		while(a[i]<flag) i++;
		while(a[j]>flag) j--;
		if(i<=j){
			temp=a[i]; a[i]=a[j]; a[j]=temp;
			i++; j--;
		}
	}
	while(i<=j);
	if(k<=j) qsort(begin,j);
	else if(i<=k) qsort(i,end);
	else qsort(j+1,i-1);
}

int main(){
	int n; scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	qsort(0,n-1);
	printf("%d\n",ans);
	return 0;
}

详细注释版

#include <iostream>
using namespace std;
int a[5000000]; // 声明一个可以存储5000000个整数的数组
int k; // 声明一个全局变量k，用来存储我们要找的是第k小的数

// 声明一个名为qsort的函数，它接受两个参数，分别表示待排序数组的开始和结束的位置
void qsort(int begin,int end){
    // 如果待排序数组只有一个元素，那么这个元素就是第k小的数
    if(begin==end) {
        printf("%d\n", a[begin]);
        return;
    }
    // 声明两个变量i和j，它们分别表示待排序数组的开始和结束的位置
    int i=begin,j=end;
    // 选择待排序数组的中间元素作为枢轴
    int flag=a[(i+j)/2];
    int temp; // 声明一个临时变量，用来交换两个元素的位置
    do{
        // 将所有小于枢轴的元素移动到枢轴的左边
        while(a[i]<flag) i++;
        // 将所有大于枢轴的元素移动到枢轴的右边
        while(a[j]>flag) j--;
        // 如果i<=j，那么交换a[i]和a[j]
        if(i<=j){
            temp=a[i]; a[i]=a[j]; a[j]=temp;
            i++; j--;
        }
    }
    while(i<=j);
    // 对枢轴左边的元素进行快速排序
    if(k<=j) qsort(begin,j);
    // 对枢轴右边的元素进行快速排序
    else if(i<=k) qsort(i,end);
    // 如果k在j和i之间，那么第k小的数就是a[j+1]
    else {
        printf("%d\n", a[j+1]);
       	return;
    }
}

int main(){
    int n; // 声明一个变量n，用来存储数组的大小
    // 使用scanf函数从标准输入读取n和k
    scanf("%d%d",&n,&k);
    // 使用for循环从标准输入读取n个整数，并存储到数组a中
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    // 调用qsort函数对数组a进行快速排序
    qsort(0,n-1);
    return 0;
}