[快速排序,分治算法] 求第 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和kscanf("%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;
}