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

一、问题分析

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