注:本文不对快速排序作任何解释,建议在对快速排序有一定了解后再阅览
一、问题分析 最简单的做法应该是直接选择先将集合排序(比如快速排序),然后直接以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); } } 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 ; int a[] = {0 ,9 ,7 ,5 ,3 ,6 ,1 }; quick_sort(a , 0, 6, k , &find ) ; if (find == -1 ){ 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