c语言实现分治法求第K大元素（详细解释）

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

一、问题分析

最简单的做法应该是直接选择先将集合排序（比如快速排序），然后直接以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代码实现：

#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

T(n) = T(n/2)+Θ(n）=>Θ(lgn)

worse-case(每次主元素都取到最大或者最小值）

T(n) = T(0) + T(n-1) + Θ(n）= T(n-1) + Θ(n)=>Θ(n^2)

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