分治法求第K大元素

本文最后更新于:2020年8月25日 晚上

注:本文不对快速排序作任何解释,建议在对快速排序有一定了解后再阅览

一、问题分析

最简单的做法应该是直接选择先将集合排序(比如快速排序),然后直接以k为下标从有序集合中获取。但是这样做时间复杂度其实是比较大的。如果要想要提升一下效率,可以考虑在快速排序的原理下稍微做点修改。

二、修改快排

1、主元素的位置特殊性

在快速排序中,第一步是选取主元素(这里记为x),然后将小于主元素x的数放在x左边,剩下的所有大于x的数放在x右边。记x的下标为x_index,这里不难发现,此时x正是集合中第x_index(如果下标从0开始算,则是x_index+1)大的元素。

2、题目情景特殊性—-只求一个数

按照快速排序的步骤,接下来是将左、右两个子集合分别重复上述的“选取主元素,其余元素按照大小放主元素左右两边”的操作,但事实题目只是要求找到一个第k大的元素。那么,左右两个子集是不是可以考虑舍去一个?(类似于二分法,只取一半)显然可以!我们可以将k与x_index进行比较,分三种情况,当

k = x_index 时,说明已经找到了

k < x_index 时,说明第k大元素在x左边的子集里,可以舍去右边部分

k > x_index 时,说明第k大元素在x右边的子集里,可以舍去左边部分

3、C代码实现:

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
#include <stdio.h>
int exchange(int *a, int i, int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
int partition(int *a, int p, int r){
int x = a[r];
int i = p-1, j;
for(j = p; j < r; j++){
if(a[j] < x){
i++;
exchange(a, i, j); //交换下标为 i和 j 两个数的位置
}
}
exchange(a, i+1, r);

return i+1;
}
int quick_sort(int *a, int p, int r, int k, int *find)
{
if(p < r){
int x_index = partition(a, p, r); //获取主元素下标
printf("主元素下标x_index=%d\n", x_index);

if(k == x_index){
*find = 1;
printf("find number k = %d\n", a[x_index]);
return 0;
}
else if(k < x_index){
quick_sort(a, p, x_index-1, k, find);
}
else if(k > x_index){
quick_sort(a, x_index+1, r, k, find);
}
}
}

int main()
{
int find = -1, k;
printf("请输入k值");
scanf("%d", &k);
k = k -1; //因为数组下标是从0开始算的,这里需要对应地做点调整
int a[] = {0,9,7,5,3,6,1}; //试验数组

quick_sort(a, 0, 6, k, &find);
//因为在整个递归过程中,存在x_index与k一直不相等的情况(实际上就是递归到底时,
//x恰好就是是k的相邻元素)。这里用find来标记是否相等。 不过无妨,到了最后,即
//便整个数组可能不是有序的,但是下标x_index和k所对应的数,已经恰好是第
//x_index大和第k大的数了,目的已经达成 ,将对应下标k的元素输出即可

if(find == -1){ //find为-1说明没有在quick_sort没有找到 k 元素
printf("find number k = %d\n", a[k]);
}


/*这里打印当前数组元素的顺序,与题目无关,仅仅是想看看数组最后的顺序 */
int i;
for(i = 0; i <= 6; i++){
printf("%d ", a[i]);
}
}

三、复杂度分析

采用主定理分析复杂度:

每次都考虑一个子问题,a=1,

  • best-case(每次主元素都取到中间值) b=2
1
2
3
T(n) = T(n/2)+Θ(n

=>Θ(lgn)
  • worse-case(每次主元素都取到最大或者最小值)
1
2
3
4
5
T(n) = T(0) + T(n-1) + Θ(n

= T(n-1) + Θ(n)

=>Θ(n^2)

事实上主元素采用random方式选取会使这个算法更加稳定。但是我看了下,它的时间复杂度好难算(我不会),所以不了不了,简单点好0_0


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!