学习笔记,仅供参考!若有错误,还请指正。
题目:
给定一个长度为 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 中利用递归函数,直到有输出结束,注意分成两部分后,其下标合起来是整个数列的下标序列,这是与单纯的快排算法的不同之处。单纯的快排是以基准点为中心分成两部分,然后分别进行再次快排,基准点没有再次参与排序,在该题中要参与。因为它是要查询。
版权声明:本文为weixin_62707591原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。