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

2023-12-14 14:48:36

求第 k 小的数

题目描述

输入 n n n 1 ≤ n < 5000000 1 \le n < 5000000 1n<5000000 n n n 为奇数)个数字 a i a_i ai? 1 ≤ a i < 10 9 1 \le a_i < {10}^9 1ai?<109),输出这些数字的第 k k k 小的数。最小的数是第 0 0 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;
}

文章来源:https://blog.csdn.net/StudyingPanda/article/details/134993466
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。