分治法查找第k小/大的数_求第k大的数 c语言 分治法

1.问题
数学语言：给无序序列集中有n个元素，查询次数m和一个整数k，1<=k<=n，找出这n个元素中第k大的元素。
2.解析
利用快速排序，可以从序列中取一个中点mid,然后把序列分成小于等于mid和大于等于mid的两部分，由两个部分的元素个数和k的大小关系可以确定这个数是在哪个部分，以此类推，进行递归查找。
3.设计

if (两边指针相交) 
		return -1;
	if (两边指针重合)
		return 当前元素;
	i = quicksort(a, l, r);//对当前序列进行快速排序
	j = i - l + 1;//当前元素在当前序列的位置大小
	if (j == k)
		返回当前值;
	else if (j > k)
		递归查找左边集合;
	else
		递归查找右边集合;

1
2
3
4
5
6
7
8
9
10
11
12
13

4.分析
最坏情况:
T(n)=T(n-1)+n-1
T(n)=O(n^2 )
平均值：
T(n)=T(n/2)+n-1
T(n)=O(n)
5.源码

#include<map>
#include<stdlib.h>
#include<iostream>
#include<vector>
1
2
3
4