拿到这个题目，我们首先想到的肯定的是对数组进行排序，然后再取第K大的数。所以在这里我们先罗列两个方法。
一，基于快排实现的。
说道排序首先想到的应该是快排，它的时间复杂度为O（NlogN），但是在这里又有一些不同，因为我们不需要度我们不关注的那一部分进行排序。
思路：根据key值把数组分割为两半，一半数字大、一半数字小。其中这两半有一半不是我们所要的，可以去除，只在我们需要的那一部分进行递归下去即可。
图片来源：http://www.csie.ntnu.edu.tw/~u91029/index.html
下面给出基于快排实现的代码：PS（快排部分是基于前面快排算法实现）
#include<iostream> #include<ctime> using namespace std; int result; void swap(int &a, int &b){ int temp = a; a = b; b = temp; } void qSort(int* A, int left, int right, int k){ if (A == NULL) return; if (left == right) result = A[left]; if (left < right){ int count = left; int key = A[left]; swap(A[left], A[right]); for (int i = left; i < right; ++i){ if (A[i] < key) continue; else { swap(A[count], A[i]); count++; } } swap(A[count], A[right]); if (count + 1 == k) { result = A[count]; return; } else if (count + 1 > k) qSort(A, left, count - 1, k); else if (count + 1 < k) qSort(A, count + 1, right, k); } } int main(){ const int n = 10; srand(time(0)); int a[n] = { 0 }; for (int i = 0; i < n; i++) { a[i] = (rand() % 30); cout << a[i] << " "; } cout << endl; int k; cin >> k; qSort(a, 0, n - 1, k); for (int i = 0; i != n; ++i){ cout << a[i] << " "; } cout << endl; cout << "第" << k << "大的值为：" << result << endl; return 0; }
二，通过计数排序法来实现
计数排序实现我们在前面实现过了，这里需要修改一下就是计数值和要与k比较，大于等于k是输出他的索引值。
#include<iostream> #include<vector> using namespace std; int result; int main(){ int a[] = { 4, 6, 6, 4, 6, 4, 9, 1, 5, 6 }; int k; cin >> k; int max = -1; for (int i = 0; i != (sizeof(a) / sizeof(int)); ++i) { if (max < a[i]) max = a[i]; } vector<int> ivec(max + 1, 0); for (int i = 0; i != (sizeof(a) / sizeof(int)); ++i) { ivec[a[i]]++; } int cmp = 0; for (int i = 0; i != ivec.size(); ++i) { cmp += ivec[i]; if (cmp >= k) { result = i; break; } } cout << "第" << k << "大的数是：" << result << endl; return 0; }
