分治法查找第k小/大的数_c++用分治法求解 第 k 大的整数** 分数 20 作者 李祥 单位 湖北经济学院 求 n 个

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

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>
#include<string>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
using namespace std;
const int maxn = 1e3 + 10;
#define ll long long
int i, j, k;
int n, m;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
int a[maxn];
int quicksort(int a[], int l, int r) {
	if (l < r) {
		i = l, j = r;
		int value = a[i];
		while (i < j) {
			while (i < j && a[j] >= value)
				j--;
			if (i < j)
				a[i++] = a[j];
			while (i < j && a[i] < value)
				i++;
			if (i < j) a[j--] = a[i];
		}
		a[i] = value;
		return i;
	}
	return -1;
}

//main
int divide(int a[], int l, int r, int k) {
	if (l > r) 
		return -1;
	if (l == r)
		return a[l];
	i = quicksort(a, l, r);
	j = i - l + 1;
	if (j == k)
		return a[i];
	else if (j > k)
		return divide(a, l, i, k);
	else
		return divide(a, i + 1, r, k - j);
}

int main() {
	cin >> n >> m;//n 是元素个数,m是查询次数
	for (i = 1; i <= n; i++)
		cin >> a[i];
	while (m--) {
		cin >> k;//第k小数
		cout << divide(a, 1, n, k) << endl;
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

Github：
https://github.com/myycjw/thekthnumber
代码解读及食用方法：
已放在源代码注释内

似乎有更加优秀的分治算法，书中提到的select算法
下方内容参考博客
https://blog.csdn.net/v_JULY_v/article/details/6431001

//copyright@ yansha && July && 飞羽
//July、updated，2011.05.19.清晨。
//版权所有，引用必须注明出处：http://blog.csdn.net/v_JULY_v。
#include <iostream>
#include <time.h>
using namespace std;
const int num_array = 13;
const int num_med_array = num_array / 5 + 1;
int array[num_array];
int midian_array[num_med_array];

void insert_sort(int array[], int left, int loop_times)
{
	for (int j = left; j < left+loop_times; j++)
	{
		int key = array[j];
		int i = j-1;
		while ( i>left && array[i]>key )
		{
			array[i+1] = array[i];
			i--;
		}
		array[i+1] = key;
	}
}
int find_median(int array[], int left, int right)
{
	if (left == right)
		return array[left];
	int index;
	for (index = left; index < right - 5; index += 5)
	{
		insert_sort(array, index, 4);
		int num = index - left;
		midian_array[num / 5] = array[index + 2];
	}
	
	int remain_num = right - index + 1;
	if (remain_num > 0)
	{
		insert_sort(array, index, remain_num - 1);
		int num = index - left;
		midian_array[num / 5] = array[index + remain_num / 2];
	}
	int elem_aux_array = (right - left) / 5 - 1;
	if ((right - left) % 5 != 0)
		elem_aux_array++;
	
	if (elem_aux_array == 0)
		return midian_array[0];
	else
		return find_median(midian_array, 0, elem_aux_array);
}

int find_index(int array[], int left, int right, int median)
{
	for (int i = left; i <= right; i++)
	{
		if (array[i] == median)
			return i;
	}
	return -1;
}

int q_select(int array[], int left, int right, int k)
{
	int median = find_median(array, left, right);
	int index = find_index(array, left, right, median);
	swap(array[index], array[right]);
	int pivot = array[right];
	int i = left; 
	int j = right - 1;  
	while (true)
	{  
		while(array[i] < pivot)
			i++;
		while(array[j] > pivot)
			j--;
		if (i < j) 
			swap(array[i], array[j]); 
		else   
			break;   
	}
	swap(array[i], array[right]);
	int m = i - left + 1;    
	if (m == k)
		return array[i];
	else if(m > k)
		return q_select(array, left, i - 1, k);  
	else  
		return q_select(array, i + 1, right, k - m);
}

int main()
{
	int array[num_array]={0,45,78,55,47,4,1,2,7,8,96,36,45};
	// 寻找第k最小数
	int k = 4;
	int i = q_select(array, 0, num_array - 1, k);
	cout << i << endl;
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

还没写过 有空填坑