所谓序列的第K大数就是对于一个给定的有N个元素的序列，为了讨论方便，假设序列元素值都不相同。这个序列的第1大数就是元素值最大的那个，第N大数就是元素值最小的那个。那么第2大就是除去最大值之外剩下元素中最大的那个。以此类推，可知第3大、第4大。。。。。。从描述中可以看出，对于查找序列的第K大数的问题，最直观的方法就是每次找到最大的那个，如果不是要找的，再从剩下的元素中再找最大的，如果还不是，则继续找。如此重复K次就能找到。那么除此之外，还有其他方法吗？
可以借鉴归并排序的思路，从要查找的序列中每次随机挑一个值出来作为参考值，把序列中比它大的值放到这个值的左边，比它小的值放到这个值的右边。然后检查一下这个值在序列中的位置，如果正好等于K，那么它就是要找的值。如果它的位置比我们要找的K要大，那么说明第K大数位于该值左边的序列中，如果它的位置比K小，说明第K大数位于该值右边的序列中。这样我们就缩小了查找范围，然后在剩下的序列中继续采用这种方法查找，直到找到为止。
以序列{11, 21, 9, 4, 33, 2, 18, 20}为例，假设我们要查找第3大元素。每次挑选第1个元素值作为参考值，对于这个序列是11。把大于11的元素都放到左边，小于11的元素都放到右边。得到序列{21，33，18，20，11，9，4，2}。11在调整后的序列中处于第5位，表示11是第5大元素。而我们要查找的是第3大元素。说明我们要找的元素在11左边的序列中，即{21，33，18，20}序列中。且在该序列中仍查找第3大元素。同样的，我们再以21作为参考元素，运用同样的规则得到{33，21，18，20}。21在该序列中处于第2位，表示21是该序列的第2大元素。而我们要查找的是第3大元素。说明我们要找的元素在21右边的序列中，即{18，20}序列中。且是该序列的第1大元素。注意，这里是需要查找第1大元素。因为21是第2大元素，所以第3大元素就是右边序列中的第1大元素。然后在{18，20}序列中重复之前的步骤，最后可以得到第3大元素就是20。
1 //在一个序列中查找第K大元素 2 #include <stdio.h> 3 int findKthNum(int* array, int size, int k); 4 int main(void){ 5 int array[] = {11, 21, 9, 4, 33, 2, 18, 20}; 6 for(int i = 1; i <= 8; i++){ 7 printf("第%d大元素是:%d ", i, findKthNum(array, 8, i)); 8 } 9 return 0; 10 } 11 12 int findKthNum(int* array, int size, int k){ 13 int key = array[0]; //参考元素 14 int flag = 0; //标识每次移动元素的终点 15 int index = 0; //标识参考元素是第几大元素 16 int tmp; 17 for(int i = 1; i < size; i++){ 18 if(array[i] > key){ 19 tmp = array[i]; 20 for(int j = i; j > flag; j--){ 21 array[j] = array[j-1]; 22 } 23 array[flag] = tmp; 24 flag = i; 25 } 26 } 27 index = flag + 1; 28 if(k == index){ 29 return array[flag]; 30 }else if(k > index){ 31 return findKthNum(&array[flag + 1], size - index, k - index); //继续在右边序列中查找第k-index大元素 32 }else{ 33 return findKthNum(array, index - 1, k); //继续在左边序列中查找第k大元素 34 } 35 }
这里使用的是移动数组元素的方法来最终确定参考元素的位置。flag是用来标识下一次移动数组元素的起点位置。