快速排序
利用快速排序(即每次都确定一个数据在从大到小的排序中所处的位置(下标))。
首先经过一遍排序,基本确定元素顺序,而后判断当前所指向数据的位置(假设为第M大,此时该位置的下标也为M)是否满足题意所求,及有M == K。若恰好为第K大,则直接返回该数据,否则,若M > K,则待求数据应当位于第M大之前;若M < K,则待求第K大位于第M大之后的数据中。(另外要注意是否要根据M的位置,更改K的值。特别是当M < K时,需要根据程序决定,是否将K变为K - M;其次,注意K值在函数传递时的情况,若数组下标从0开始,则应该改变K为K - 1)

class Solution { public: int QuickSort(vector<int> a, int l, int r, int K) { int left = l, right = r, s = a[l]; while (left &lt; right) { while (left &lt; right &amp;&amp; a[right] &lt; s) right--; if (left &lt; right &amp;&amp; a[right] &gt; s) a[left] = a[right]; while (left &lt; right &amp;&amp; a[left] &gt;= s) left++; if (left &lt; right &amp;&amp; a[left] &lt; s) a[right] = a[left]; } int res = 0; a[left] = s; if (left == K) return a[left]; else if (left &gt; K) { res = QuickSort(a, l, left - 1, K); } else { res = QuickSort(a, left + 1, r, K); } return res; } int findKth(vector<int> a, int n, int K) { int ans; ans = QuickSort(a, 0, n - 1, K - 1); return ans; } };